cool hit counter The soft exam on the way] - Compilation principles_Intefrankly

The soft exam on the way] - Compilation principles

Copyright: This is an original post by the blogger and may not be reproduced without the blogger's permission.

Compilation principles are broadly divided into the following points in the soft exam: grammar、 Grammar pushing down trees and arithmetic priority

Here's a summary of those three aspects.


basic element

It is important to first understand the two most basic elements of grammar: the non-terminal and the final.

A non-terminator can be understood as an element that can still be split, and is generally denoted by an uppercase letter; a terminator can of course be seen as an element that cannot be split, and a terminator cannot be converted to another state or replaced by another quantity, and is generally denoted by a lowercase letter.

In the figure, it can be seen that a grammar G is a quadruple consisting of VN,VT,P,S, where VN represents the set of non-terminal operators; VT represents the set of final operators; P is a rule [α → β, α ∈ (VN ∪ VT) and α contains at least one non-terminal operator, β ∈ (VN ∪ VT),]; and S is a symbol [S ∈ VN].

grammar types

0 type (e.g. blood type) grammar( phrase grammar): an grammarG=(VN,VT,P,S) in, If each of its generating equationsα→β all of them are in lineα∈(VN∪VT) yetα contains at least one non-terminator,β∈(VN∪VT), So call itG It's a0 type (e.g. blood type) grammar, in caseG0({S,A,B},{a,b,c},P,S) The generating equation forS→Aa,Aa→B,Ab→abc,B→aba, or soG0 It's a0 type (e.g. blood type) grammar。

Type 1 grammar (context-dependent grammar): type 1 grammar adds an extra condition to type 0 grammar that the length of α must be greater than or equal to the length of β. In the above example, G0({S,A,B},{a,b,c},P,S) does not conform to type 1 grammar because it has Aa→B. The number of symbols on the left side of "→" must be less than or equal to the right side.

2 type (e.g. blood type) grammar( Contextual irrelevance grammar):2 type (e.g. blood type) grammar (located) at1 type (e.g. blood type) grammar An additional condition was added to the,α Must be a non-terminator, preceding exampleG0 In because of theAb→abc,Ab Not a non-terminator, consequentlyG0({S,A,B},{a,b,c},P,S) not conforming2 type (e.g. blood type) grammar。“→” The symbol on the left must be a non-terminator。

3 type (e.g. blood type) grammar( informal grammar),3 type (e.g. blood type) grammar (located) at2 type (e.g. blood type) grammar An additional condition was added to the,β If a terminator and a non-terminator are included in, Non-terminators are either all on the left, Either that or they're all on the right.。 for exampleA→aB,B→Bc, Then it doesn't fit3 type (e.g. blood type) grammar, But if there isA→aB,B→cB, Then it fits3 type (e.g. blood type) grammar。

As can be seen from the introduction, the regular form is actually another expression of the grammar, and A → xB, B → y can be deduced as the regular form A → xy.

Grammar pushing down trees

It can be done directly with a grammar And a chart to understand:

For the grammar G = ({S,A},{a,b},P,S), we have S → aAS|a and A → SbA| SS|ba, splitting it gives: s→aAS, S→a, A→SbA, A→SS, A→ba, which constructs the pushdown tree for the sentence type aabAa as

Of course, to get sentence patterns from a grammar book, just arrange the leaf nodes directly from left to right.

algorithm prioritization analysis


FIRSTVT(A): for the non-terminator A, the right-hand side of each derivation has A → a... or A → Ca..., then a belongs to the FIRSTVT set.

LASTVT(B): for the non-terminator B, the right-hand side of each derivation has B →... b or B →... bC, then b belongs to the LASTVT set.

priority relationship

The operations of the three priority relations are.

≑ relation: look directly at the right part of the generating equation, if there is A →... ab... Or A→... aBb... , then we have a≑b.

⋖ relation: when A →... aB... when there is a ⋖ b for every b ∈ FIRSTVT(B).

⋗ relation: when A →... Bb... when for every a ∈ FIRSTVT(B) there is a ⋖ b.

The above is only a summary of what I learned in the video, understanding is not specific enough, I hope to be able to eat the knowledge thoroughly in the process of reading the book and doing the questions later.

You're the best on the road to the soft exam!

1、An introduction to depthfirst search
2、Resolved UISwitch executes setOnanimated without any effect or animation
3、Teach you easy and quick understanding of the eta coin
4、Can drones help proctor college entrance exams against cheating
5、Analysis of Java Concurrency Implementation of Condition

    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送