ZUCC_ Principles of compiling language and compilation_ Experiment 04 language and grammar

Compiling language principle and compiling experiment report

Course name	Programming language principle and compilation
Experimental projects	Language and grammar

The experiment purpose

• Understand the history of grammar
• Understand production rules
• Master the leftmost derivation , Rightmost derivation
• Grasp the ambiguity of grammar
• Master the classification and level of grammar

Experimental content

One 、 Read the courseware and complete the exercises after class

1、 Give language L2={a^n b^m| m≥n≥1} Grammar

$$\begin{gathered} P_1:S\to AB \\ A\to aAb\mid ab \\ B\to bB\mid \epsilon \end{gathered}$$

2、 Give language L1={a^(2n+1)|n≥0} Grammar

$$P_2:A\to aAa\mid a$$

3、 Give language L3={a^n b^m c^k| n,m,k≥0} Grammar

$$\begin{gathered} P_3:S\to ABC \\ A\to AA\mid a\mid \epsilon \\ B\to BB\mid b\mid \epsilon \\ C\to CC\mid c\mid \epsilon \end{gathered}$$

4、 Write a grammar , Make its language a set of positive even numbers , Each even number does not begin with 0 start

$$\begin{gathered} P_4:S\to N \\ N\to 2\mid 4\mid 6\mid 8\mid NM \\ M\to 0\mid 2\mid 4\mid 6\mid 8 \end{gathered}$$

5、 Give language L={1^n 0^m 1^m 0^n | n,m≥0} Grammar

$$\begin{gathered} P_5:S\to 1S0\mid 0A1\mid \epsilon \\ A\to 0A1\mid \epsilon \end{gathered}$$

6、 Give language L={ WaW^t | W∈{0|1}* }, among W^t Express W The inverse grammar of

$$P_6:S\to a\mid 0S0\mid 1S1$$

7、 Grammar G[A]=({A},{a,b},{A→bA | a}, A) What is the generated language ？

$$L(G[A])=\left\{b^{n}a\mid n\ge 0\right\}$$

8、 Grammar G[N] by :

$$\begin{gathered} N\to ND\mid D \\ D\to 0\mid 1\mid 2\mid 3\mid 4\mid 5\mid 6\mid 7\mid 8\mid 9 \end{gathered}$$

(1) G[N] What is the generated language ？

$$L(G[A])=\left\{\alpha \mid \alpha byCountwordstrand\right\}$$

(2) Give sentences 0127 Leftmost of 、 Rightmost derivation .

Leftmost inference
$$N*ND*NDD*NDDD*DDDD*0DDD*01DD*012D*0127$$
Rightmost derivation
$$N*ND*N7*ND7*N27*ND27*N127*D127*0127$$

9、 Known grammar G[S]=( {A,B},{a,b,c,d}, P, S ) , among P by :

$$\begin{gathered} S\to AB \\ A\to aAb\mid ab \\ B\to cBd\mid cd \end{gathered}$$

The grammar What is the generated language ？
$$L(G[S])=\left\{a^n{b}^n{c}^m{d}^m\mid n,m\ge 1\right\}$$

10、 Known grammar G[E]：

$$\begin{gathered} E\to E+T\mid E-T\mid T \\ T\to T\ast F\mid T/F\mid F \\ F\to (E)\mid i \end{gathered}$$

prove E+T*F It's a sentence pattern , A phrase that points out this sentence pattern 、 Direct phrases and handles
$$\begin{gathered} E*E+T*E+T\ast F \\ shortlanguage:E+T\ast F、T\ast F \\ straightPick\; upshortlanguage:T\ast F \\ sentenceHandle:T\ast F \end{gathered}$$

11、 Known grammar G[S]：

$$\begin{gathered} S\to (AS)\mid (b) \\ A\to (SaA)\mid (a) \end{gathered}$$

Try to find the symbol string (a) and (A((SaA)(b))) 's phrases ﹑ Direct phrases and handles ( If any )

• Symbol string (a)) Not a grammatical sentence pattern , So it has no phrases ﹑ Direct phrases and handles

• $$\begin{gathered} S*(AS)*(A(AS))*(A(A(b)))*(A((SaA)(b))) \\ shortlanguage:(A((SaA)(b)))、((SaA)(b))、(SaA)、(b) \\ straightPick\; upshortlanguage：(SaA)、(b) \\ sentenceHandle：(SaA) \end{gathered}$$

12、 With grammar G[S]: S→iSeS| iS | i, Proof grammar G[S] Ambiguous .

13、 With grammar G[N]:

$$\begin{gathered} N\to SE\mid E \\ S\to SD\mid D \\ E\to 0\mid 2\mid 4\mid 6\mid 8\mid 10 \\ D\to 0\mid 1\mid 2\mid 3\mid 4\mid 5\mid 6\mid 7\mid 8\mid 9 \end{gathered}$$

(1) Proof grammar G[N] Ambiguous .

(2) What language does this grammar describe ？

The language described by this grammar is a set of all unsigned even numbers ( Sure 0 start ).

(3) Try to write another grammar G’ send L(G’)=L(G) And G’ There is no ambiguity

$$\begin{gathered} N\to SE\mid E \\ S\to SD\mid D \\ E\to 0\mid 2\mid 4\mid 6\mid 8 \\ D\to 0\mid 1\mid 2\mid 3\mid 4\mid 5\mid 6\mid 7\mid 8\mid 9 \end{gathered}$$

Two 、 Read the textbook to understand the linear language SPL

The correspondence between code and grammar

The code is equivalently transformed into a tree structure to describe , Focus only on statements and expressions , Formed a linear program .

Production rules of grammar

And type Type defined relationships

Grammar can be translated directly into the definition of data structure , Each grammar symbol corresponds to one of the data structures typedef, for example ：

And one of the A_stm It's actually a structure .

And the interpreter interp The relationship between

Through the interpreter , Using constructors to interpret execution languages , And its environment 、 Abstract syntax 、 The recursion of tree data structure is demonstrated .

3、 ... and 、 Refer to the simple language interpreter Naive.fs Code , Try to write the grammar

Four 、 What are the following grammatically generated languages

G1 : S-> AB
    A -> aA|ε
    B->bc|bBc

G2: S ->aA|a
    A ->aS

G1： arbitrarily a Characters （ Include 0 individual ） After follow n individual b and c,n At least for 1

G2： Any odd number a（ At least one ） Composed string