S-> NP VP VP->VNP NP=> NAME NP->ART N NAME-> John V->ate Art-> the N-> cat NP VP NAME NP ate ARt N the cat
S NP VP NAME John V NP ate ART N the cat S -> NP VP VP -> V NP NP -> NAME NP -> ART N NAME -> John V -> ate ART -> the N -> cat
推导和语法树 ●对于推导中的每个句程;,我们都可以构造出一个结 果为fo;吾法树 a;-1=X1X2…XkX→8B=112)ma1=X1X2…-1BX1+1…k
推导和语法树 对于推导中的每个句型 ，我们都可以构造出一个结 果为 的语法树 17
推导与语法树例子 E→-E→-(E)→-(E+E)→-(id+E)→-(id+id) E E E E E E E E E E C E E E+ E E+ E E+ E id 图4-4推导(4.8)的语法分析树序列
推导与语法树例子 18
词法分析和语法分析比较 阶段 输入 输出描述体系 词法分析源程序符号串词法单元序列正则表达式 句法分析 词法单元序列 语法树上下文无关文法 文法比正则表达式描述能力更强 正则表达式描述词法单元比较简洁 基于正则表达式构造的词法分析器效率更高 正则表达式适合描述词法结构,文法适合描述嵌套 结
词法分析和语法分析比较 阶段 输入 输出 描述体系 词法分析 源程序符号串 词法单元序列 正则表达式 句法分析 词法单元序列 语法树 上下文无关文法 19 文法比正则表达式描述能力更强 正则表达式描述词法单元比较简洁 基于正则表达式构造的词法分析器效率更高 正则表达式适合描述词法结构，文法适合描述嵌套 结构
补充 文法的类别, Chomsky文法类 o型文法(短语结构文法),α→β 型文法(上下文相关文法),αAβ→aVβ 2型文法(上下文无关文法),A→y 3型文法(正则文法),A→t,A→tB
补充 文法的类别，Chomsky文法类 0型文法(短语结构文法)， α →β 1型文法(上下文相关文法)， αAβ → αγβ 2型文法(上下文无关文法)， A →γ 3型文法(正则文法)，A →t, A →tB 20