编译原理简明教程(第2版)[冯秀芳,崔冬华,段富][电子教案]第2章.ppt

算法6. 消除左递归 G[S]中有:A→Aβ|α,其中α, β∈V*, α不以A开头 修改为:A → αA’ A’→ βA’|ε 例: E →E+T|E-T|T E →TE’ T → T*F|T/F|F → E’ → +TE’ | -TE’ | ε F → (E)|i T → FT’ T’ → *FT’ | /FT’ | ε F → (E) | i 2.4.5 扩充的BNF表示法 在BNF上发展起来,相同表达效力,结构上更简单，清晰. 一.专用符号{t}------t可重复任意次 [t]-------t可出现0次或1次 ( )-------提因子 例:G[N]: N →ND|D N → D{D} D → 0|1|…|9 D → 0|1|…|9 例:G[E]: E → T|T+E E → T[+E] T → F|F*T T → F[*T] F → i|(E) F → i|(E) 例: A → αβ1| αβ2|…|αβn A → α (β1| β2|…|βn ) 二. 扩充BNF表示法的用途. 消除左递归,使文法在自顶向下分析过程中，能进行分析处理. 例:G[E]: E→T{+T} T → F{*F} F → i|(E) 2.5 文法和语言的Chomsky分类 四类文法对应四类语言. 2.5.1 0型文法与0型语言(图灵机) 定义:文法G[S],P中每条规则形如: α→β, α∈V+, β∈V* 则称G为0型文法(or短语结构文法or无限制性文法)记PSG. 产生的语言为0型语言(or短语结构语言or无限制性语言)记L0(G) 例[2-5]: P={S→ACaB, Ca → aaC, CB → DB CB → E, aD → Da, AD → AC, aE → Ea, AE → ε } S ACaB AaaCB AaaE AaEa AEaa aa, S aaaa L0(G)={a2n|n0} 尽管0型文法不足以描述自然语言，但对程序设计语 言的描述而言又太一般化,所以须对规则的形式加以限制. + 2.5.2 1型文法与1型语言（线性界限自动机） 定义：文法G[S]中每个规则即为： αWβ→αωβ ,W∈VN ，α，β∈V*,ω∈V+ 则称G为1型文法（或上下文有关文法)→CSG产生的语言称为1型语言L1（G）（或上下文有关语言，前后文有关语言） 在自然语言中，一个句子或一个单词的语法性质往往和它所处的上下文有密切的关系，所以描述自然语言的文法一定是上下文有关文法。 例：G[S]： S→aSBC|aBC G[S]是1型文法 CB→DB DB→DC DC→BC aB→ab bB→bb bC→bc cC→cc S?aBC?abC?abc S?aSBC?aaBCBC?aabCBC ?aabDBC?aabDCC?aabBCC ?aabbcC?aabbcc … … L1(G)={anbncn|n≥1} 2.5.3 2型文法和2型语言 （下推自动机，程序设计语言） 定义: 文法G[S] 中每一个规则形如： A→α ，A∈VN ， α∈V+ 则称G为2型文法（或上 下文无关语言）L2（G）。 注: 有些书中α∈V* ，即允许出现α→ε的规则。大部