The second chapter of the compiling principle is the answer to the problem

The second chapter of the compiling principle is the answer to the problem The second chapter of the compiling principle is the answer to the problem Chapter 2. Problem solving Grammar G [S] is: S - > Ac | aB A - > ab B - > BC Write the whole element of L (G [S]). [the] S = > Ac = > ABC Or S = > aB = > ABC So L (G [S]) = {ABC} For example, this is the case for the problem Grammar G [N] is: N - > D | ND D - >, 0, |, 1 |, 2 |, 3 b|, 3 b|, 3 b|, 3 |, 3 b|, 3 b|, 3 b|, 3 b|, 3 b|, 3 b|, 3, 3, 3, 3, 3, 3, 3, 3 What is the language of G [N]? [the] The language of G [N] is V +. V equals {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} N = > ND = > NDD... = > NDDDD... D = > D... D For example, this is the first time that you have to go to the end of the line The known grammar G [S] : S, dAB A, aA |, A, B, and epsilon | bB Q: what is the corresponding normal form? Can G [S] be rewritten to be equivalent formal grammar? [the] The normal type is daa * b *; The corresponding regular grammar is (simplified by automaton) : G [S] : S, dA A, A, B, B, B, B, B, B, B, B, B, B, B, B, B, B, B, B, B, B, B, B, B, B, B, B, B, B, C, B, B, B, B, C, B, B, B, C It can also be (observed) : G [S] : S to dA A to A | aA | aB B to bB | epsilon = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = The known grammar G [Z] : Z - > aZb | ab Write down all the elements of L (G [Z]). [the] Z = > aZb = > aaZbb = > aaa. Z... BBB = > aaa.. Ab... BBB L (G [Z]) = {anbn | n > = 1} = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = The context of the language {anbncm | n > = 1, m > = 0}. [analysis] This problem is not very difficult, it is the basic concept of the following irrelevant grammar. Context-free grammar is the basic definition of: A - > beta, A ?.vn, beta ? (.vn ? Vt) *, pay attention to the key problem is to guarantee the establishment of the anbn, namely "the number of A and b is equal", therefore, can use A bar as A - > aAb | ab production can be solved. [the] The constructs context-free grammar is as follows: S - > AB | A A - > aAb | ab B - > Bc | c [expansion] All such questions should be carried out in this way, which can be used as a basic representative. The basic idea is this: Meet anbncm, because a and b requires equal Numbers, so they should be performed as a whole unit, the cm as another unit, preliminary production should be written as the S - > AB, which launched a anbn, b launched cm. Because m is equal to 0, so this is going to be rewritten as s->, AB, b0, A. And then if you think about A, all of the questions that require an equal number of end characters should be written as A minus >, aAb, | ab, and B - > Bc, | c, for B. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Write a grammar so that the language is a set of even integers. Requirements: (1) allowing 0 to start; (2) no beginning of 0. [the] (1) the grammar of the set of accidentally positive integers that start with 0 E - > NT | G | SFM T - > NT | G N minus >, D, |, 1 |, 3 |, 5 |, 7 | 9 D - > 0 | G 8 G - > 2 4 6 | | | S - > NS | epsilon. F - >, 1 |, 3 |, 3 |, | 7, |, 9 | G M - > M0 | 0 (2) the grammar of a set of accidentally positive integers that does not allow 0 E - > NT | D T - > FT | G N minus >, D, |, 1 |, 3 |, 5 |, 7 | 9 D - > 2 | | | 6 four to eight F - > N | 0 G - > D | 0 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Known grammar G: E minus > E plus T | E minus T | T T minus > T times F F - > (E) | I Try to derive the derivation and syntax tree of the following expression (1) I; (2) I + I (3) I + I (4) I + (I + I) [the] (1) E = > T = > F = > I (2) E = > E + T = > T + T = > T = > F + T = > F + T = > I * F + T = > (3) E = > E + T = > T + T = > F + T = > I + T = > I + T = > I + T = > I + F = > I + I * F = > I + I *(4) = > E + E T T + T = = > > F + T + T = = > I > = > I + I + F (E) (E + T) = = > I + I + (T + T) = > > I + + T (F) = > I + (I + T) = > I + I + + F (I) = > (I + I) I construct two syntax trees for the sentence I + I * I to prove that the following grammar G [< expression >] is ambiguous. < expression > - > < expression > < < expression > < expression >) < operator >-> + | - | * | / [the] You can construct two different and the most right derivations for the sentence I + I * I: The right is 1 < expression > = > < expression > < operator > < expression > > < expression > < operator > I > < expression > * I > < the expression > < the expression > * I > < the expression > < operator > I * I It's going to be equal to > That's equal to > I plus I times I The right is 2 < expression > = > < expression > < operator > < expression > > < expression > < operator > < expression > < operator > < expression > > < the expression > < operator > < expression > < the operator > I > < the expression > < the expression > * I > < the expression > < operator > I * I It's going to be equal to > That's equal to > I plus I times I So, this method is ambiguous. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Grammar G [S] is: S - > Ac | aB A - > ab B - > BC Is this method justified? Why is that? [the] For the string of ABC (1) S = > Ac = > ABC (2) S = > aB = > ABC There are two very different right derivations So, this method is ambiguous. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Consider the following context-free grammar: S minus > (1) shows how the string aa + a * is generated by this method and constructs the syntax tree for the string. (2) what is the language of G [S]? [the] (1) the most right-hand derivation of the series aa + a * in this document is as follows S = > SS * = > Sa * = > SS + a * = > aa + a * (2) the language generated by this method is the inverse polish of addition and multiplication. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Make grammar G [E] for: E - > E + T | E - T T minus > T times F F - > (E) | I Prove that E + T * F is a sentence pattern and points out all the phrases, direct phrases and handles of this sentence pattern. [the] This sentence pattern corresponds to the grammar tree like the right. Or: because there is a derivation sequence: E = > E + T = > E + T * F, so E + T * F The phrase of this sentence is: E + T * F. The expression for T is T times F, Direct expression: T * F; It is. Handle: T * F The known grammar G [E] : E - > ET + - > TF * | | T T F F - > F ^ | a Test certificate: FF ^ ^ * is the grammar of the sentence, pointed out that the handle to the phrase, simple phrases and sentence patterns. [the] The syntax tree for this pattern is as follows: The sentence patterns relative to E phrases have FF ^ ^ *; Relative to the T phrases have FF ^ ^ *, F; Relative to the F phrases have F ^; F ^ ^; Simple phrases have F; F ^; Handle for F. A context independent grammar generates sentences for abbaa: (1) the most left derivation of the series abbaa is derived. (2) what are the elements of the generated set P? (3) find out all the phrases, direct phrases, and handles of the sentence. (1) the most left derivation of the series abbaa: S = > ABS = > ABS = > aSBBS = > a epsilon BBS = > a epsilon > a epsilon BBS = > a epsilon bbAa = > a epsilon bbAa The right is: S = > ABS = > ABAa = > ABAa = > ASBBaa = > ASBBaa = > ASBBaa = bbbbbaa = > A = bbbbbaa = > A = bbbbbaa = >, bbaa = bbbbbaa = >, A) (2) the production is: S, ABS, |, | epsilon A - A B - > SBB | B(3) the phrase of the sentence is a1b1b2a3, a1, b1, b2, b1b2, a2a3, a2. The direct phrases are a1, b1, b2, and a2; Handle is a1. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = The context grammar that generates the following languages is given. (1) {anbnambm, | n, m > = 0} (2) {1n01 m0n, m > = 0} (3) {WaWr | W belongs to {0 | a} *, Wr for W inverse} [the] (1) {anbnambm | n, m > = 0} S - > AA A - > aAb | epsilon. (2) {1nm-1m0n | n, m > = 0} S - > 1 s0 | A A - > 0 a1 | epsilon. (3) {WaWr | W belongs to {0 | a} *, Wr for W inverse} S - > 0 s0 | 1 | s1 epsilon = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Give three types of grammar that produce the following languages. (1) {an | n > = 0} (2) {anbm | n, m > = 1} (3) {anbmck | n, m, k > = 0} [the] (1) the three types of grammar: (1) {an | n > = 0} are: S - > aS | epsilon. (2) {anbm | n, m > = 1}. S-> aA A - > aA | bB B - > bB | epsilon. (3) {anbmck | n, m, k > = 0}. A-> aA | bB b1 cC | epsilon B - > bB | cC | epsilon. C - > cC | epsilon. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Construct a grammar of any length of a, b string, and make it | a | < = | b | < = 2 | a | "| a |" means the number of a characters; "| b |" is the number of b characters. [analysis] The number of b is between a and 2a, so you should think of the form as a form of aSBS and BSaS, and b is one to two b, which satisfies the conditions. [the] As described in the analysis, the grammar is as follows: S - aSBS | BSaS | epsilon. B - > bb | B First production for recursive definition, because the B in the second production is defined as 1 or 2 B, so the first production can ensure that the number of B at the | | | | a and 2 a, between the location of a and B can be arbitrary configuration, so this method is the petitions, pay attention to the first production to be included in the s. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = The following grammar produces the number of a and the number of b's not empty a, b strings S - > aB | bA B - > bS aBB | | B A - > aS | | A bAA The non-terminal B is going to be one more than the number of B, and a is the other way around. It means that the method of this article is two meanings. Modify the above grammar to make it unambiguous and produce the same language. (a slight modification means not adding a non-terminal.) [the] There are two different derivations of the sentence aabbab. S = > aB = > aabbS = > aabbS = > aabbaB = > aabbaB S = > aB = > aabbAB = > aabbAB = > aabbAB = > aabbAB That is, it can produce two different syntax trees, so it is ambiguous. The modified unambiguous grammar is as follows: S - > aBS | bAS | aB | bA B - > aBB | B A - > bAA | A = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Give the definition of the 0, 1, 2, 3 grammar. [the] Chomsky divides grammar into type, type 0, type 1, type 2 and type 3, type 0, type 1, type 1, type 2, type 2, type 2, type 2, type 2, type 2, type 2, type 2, type 2, type 2, type 2, type 2, type 2, and type 2, type 2, type 2, type 2, type 2, type 2, type 2, type 2, type 2, type 2, If each of its generating alpha - > beta is the structure of the alpha ? (VnUVt) * and containing at least a non-terminal, and beta ? (VnUVt) *, we say that G = (n,.vn, S, the delta) is a type 0 grammar. Type 0 grammar is also called phrase grammar. A very important theory is that the ability of the 0 grammar is the same as the Tunring machine. Or, any 0-type language is recursively enumerable; Conversely, the recursive enumeration set must be a 0 language. If you add the 0 grammar to the following I bar,We have to have type I grammar: Any production of G will satisfy | alpha | < = | beta |. The s-> epsilon exception, but S is not allowed to appear in any generated right. Any production of G is A minus > beta, A is Vn, and beta is the same Any resulting form of G is A minus > aB or A minus > A, where A, B, is Vn Type 1 grammar is also known as contextual grammar. This grammar means that it is important to consider the context when substituting for the non-terminal, and not to be replaced by empty strings. The type 2 grammar does not need to be concerned with the context when replacing the non-terminal. Type 3 grammar is also called linear grammar.