第四章语法分析.pptxVIP

第四章语法分析

第四章语法分析本章内容上下文无关文法自上而下分析和自下而上分析围绕分析器的自动生成展开词法分析器记号取下一个记号源程序分析树前端的其余部分分析器中间表示符号表

上下文无关文法4.1~4.3

4.1上下文无关文法4.1.1上下文无关文法的定义正则式能定义一些简单的语言，能表示给定结构的固定次数的重复或者没有指定次数的重复 例：a(ba)5,a(ba)*正则式不能用于描述配对或嵌套的结构 例1：配对括号串的集合 例2：{wcw|w是a和b的串}

4.1上下文无关文法上下文无关文法是四元组（VT,VN,S,P）VT: 终结符集合VN: 非终结符集合S: 开始符号，非终结符中的一个P: 产生式集合，产生式形式:A??例({id,+,?,?,(,)},{expr,op},expr,P)expr?expropexpr expr?(expr)expr??expr expr?idop?+ op??

4.1上下文无关文法简化表示expr?expropexpr |(expr)|?expr|idop?+|?简化表示E?EAE|(E)|?E|idA?+|?

4.1上下文无关文法文法书写上的约定终结符字母表中的小写字母，如a，b，c黑体串，如id,while数字0,1,…,9标点符号，如括号，逗号等运算符号，如+,-等非终结符字母表中的大写字母，如A,B,C字母S，并且通常代表开始符号小写字母的名字（斜体），如expr,stmt

4.1上下文无关文法文法书写上的约定字母表中后面的大写字母，如X，Y，Z，可以是终结符或非终结符字母表中后面的小写字母，如u，v…z可代表终结符号串小写希腊字母，如a，b，可代表文法的符号串对于A?a1，A?a2，...A?an可以写成A?a1|a2|…|an

4.1上下文无关文法4.1.2推导（自顶向下）把产生式看成重写规则，把符号串中的非终结符用其产生式右部的串来代替例 E?E+E|E?E|(E)|?E|idE??E??(E)??(E+E)??(id+E)??(id+id)概念 S?*?、S?+w，于是??*???*b，且b?γ,则??*γ

4.1上下文无关文法4.1.2推导概念 上下文无关语言A→γ,且a、b是任意符号串，则aAb?aγb由上下文无关文法生成的语言是上下文无关语言等价的文法如果两个文法产生同样的语言，则两个文法等价句型文法G的开始符为S，S?*?，?可能含有非终结符，则?叫做文法G的句型。

4.1上下文无关文法例E?E+E|E?E|(E)|?E|id最左推导 E ?lm?E?lm?(E)?lm?(E+E) ?lm?(id+E)?lm?(id+id)最右推导 E ?rm?E?rm?(E)?rm?(E+E) ?rm?(E+id)?rm?(id+id)

4.1上下文无关文法4.1.3分析树例E?E+E|E?E|(E)|?E|idEE?()EEE+idid

4.1上下文无关文法4.1.4二义性id?id+id E ?E?E E ?E+E ?id?E ?E?E+E ?id?E+E ?id?E+E ?id?id+E ?id?id+E ?id?id+id ?id?id+id 两个不同的最左推导

4.1上下文无关文法4.1.4二义性id?id+id E ?E?E E ?E+E ?id?E ?E?E+E ?id?E+E ?id?E+E ?id?id+E ?id?id+E ?id?id+id ?id?id+id 两棵不同的语法树EEE*+EEidididEEidE*+EEidid

4.2语言和文法文法的优点文法给出了精确的，易于理解的语法说明自动产生高效的分析器可以给语言定义出层次结构以文法为基础的语言的实现便于语言的修