源语言程序：源语言编写的，有待翻译的程序

目标语言程序：源程序通过翻译加工后生成的程序

翻译程序：指用来把源程序翻译为目标程序的程序

解释程序：这也是一种翻译程序，用样是将高级语言源程序翻译成机器指令。它与编译程序的不同点就在于：它是边翻译边执行的，即输入一句，执行一句，直至将整个源程序翻译并执行完毕

编译程序：源语言为高级语言，目标语言为某台计算机上面的汇编语言或机器语言，则此翻译程序称为编译程序

词法分析程序：输入源程序，拼单词、检查单词和分析单词，输出单词的机内表达式

语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息

语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表

中间代码生成程序：按照语义规则，讲语法分析程序分析出的语法单位转换为一定形式的中间语言代码。

代码优化程序：对中间代码进行等价变化处理

目标代码生成程序：将优化后的中间代码程序转换为目标代码程序

符合表管理程序：建立、填写和查找等一系列表格工作。

出错管理程序：处理和校正源程序中存在的词法、语法和语义错误。

1.文法G(Z):Z->aZb|ab定义的是什么样的语言？

L ( G ) = { a n b n ∣ n ≥ 1 } L(G)=\{a^nb^n|n\geq1\} L(G)={anbn∣n≥1}

2.写出文法G(Z):Z->AB A->aBb|ab B->cB|b 定义的是什么样的语言

L ( G ) = { a b c n b ∣ n ≥ 0 } , { a c m b 2 c n b ∣ m ≥ 0 & n ≥ 0 } L(G) = \{abc^nb|n\geq0\},\{ac^mb^2c^nb|m\geq0\&n\geq0\} L(G)={abcnb∣n≥0},{acmb2cnb∣m≥0&n≥0}

3.写出文法G(S):S->aAb A->aAb|b定义的是什么样的语言

L ( G ) = { a n b n + 1 ∣ n ≥ 1 } L(G) = \{a^{n}b^{n+1}|n\geq1\} L(G)={anbn+1∣n≥1}

(1) { a n b m c 2 m ∣ n , m ≥ 0 } \{a^nb^mc^{2m}|n,m\geq0\} {anbmc2m∣n,m≥0}

S − > A B ∣ ε S->AB|\varepsilon S−>AB∣ε A − > a A b ∣ a b A->aAb|ab A−>aAb∣ab B − > b B c ∣ b c B->bBc|bc B−>bBc∣bc

(2) { w c w R ∣ w ε { a , b } ∗ } \{wcw^R|w\varepsilon\{a,b\}^{\ast}\} {wcwR∣wε{a,b}∗}

S − > a S a ∣ b S b ∣ c S->aSa|bSb|c S−>aSa∣bSb∣c

(3) { a n b m c k ∣ n = m 或 m = k } \{a^nb^mc^k|n=m或m=k\} {anbmck∣n=m或m=k}

S − > A B ∣ D E ∣ ε S->AB|DE|\varepsilon S−>AB∣DE∣ε A − > a A b ∣ a b A->aAb|ab A−>aAb∣ab B − > c B ∣ c ∣ ε B->cB|c|\varepsilon B−>cB∣c∣ε D − > a D ∣ a ∣ ε D->aD|a|\varepsilon D−>aD∣a∣ε E − > b E c ∣ b c E->bEc|bc E−>bEc∣bc

1.构造下面语言的上下文无关文法 (1) { a n b n ∣ b ≥ 0 } \{a^nb^n|b\geq0\} {anbn∣b≥0}

S − > a S b ∣ ε S->aSb|\varepsilon S−>aSb∣ε

(2) { a m b n ∣ m ≥ n ≥ 0 } \{a^mb^n|m{\geq}n{\geq}0\} {ambn∣m≥n≥0}

S − > A B S->AB S−>AB A − > a A ∣ a ∣ ε A->aA|a|\varepsilon A−>aA∣a∣ε B − > a B b ∣ a b ∣ ε B->aBb|ab|\varepsilon B−>aBb∣ab∣ε

已知如下文法 G [ E ] : E − > E + T ∣ T G[E]:E->E+T|T G[E]:E−>E+T∣T T − > T ∗ F ∣ F T->T{\ast}F|F T−>T∗F∣F F − > ( E ) ∣ a F->(E)|a F−>(E)∣a (1)求(a+a)*(a+a)的最右推导

(2)求(a+a)*(a+a)的语法树

略