文档介绍：该【上次课程内容回顾公开课一等奖课件赛课获奖课件 】是由【读书百遍】上传分享，文档一共【38】页，该文档可以免费在线阅读，需要了解更多关于【上次课程内容回顾公开课一等奖课件赛课获奖课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。上次课程内容回忆
一、二义性与二义性的消除
导致二义性的原因－文法符号缺乏明确的优先级和结合性
消除二义性的措施：
改写二义文法为无二义文法
为文法符号规定优先级和结合性
变化语言的构造或书写方式
二、语言与文法的分类
正规式、CFG、CSG
从计数问题看三者之间的关系
1
形式语言与自动机简介
对0型文法施加如下第i条限制，即得到i型文法。
G的任何产生式α→β（S→ε除外）满足|α|≤|β|；
G的任何产生式形如A→β，其中A∈N，β∈(N∪T)*；
G的任何产生式形如A→a或者A→aB(或者A→Ba)，其中A和B∈N，a∈T。 ■
文法、语言与自动机
文 法
语 言
自 动 机
短语文法 (0型)
短语结构语言
图灵机
CSG (1型)
CSL
线性界线自动机
CFG (2型)
CFL
下推自动机
正规文法 (3型)
正规集
有限自动机
若文法G=(N，T，P，S)的每个产生式α→β中，均有α∈(N∪T)*，且至少具有一种非终止符，β∈(N∪T)*，则称G为0型文法。
2
形式语言与自动机简介（续）
L3={anbncn|n≥1}
L3'={ambmcn|m,n≥1} （A→AC A→aAb|ab C→cC|c）
L3''={akbmcn|k，m，n≥1} （a+b+c+ ）
L3可用下述CSG描述：
S→aSBC (1)
S→aBC (2)
CB→BC (3)
aB→ab (4)
bB→bb (5)
bC→bc (6)
cC→cc (7)
句子akbkck 的推导：
S =>...=> ak-1S(BC)k-1 (by 1)
=> ak(BC)k (by 2)
=>...=> akBkCk (by 3)
=> akbBk-1Ck (by 4)
=>...=> akbkCk (by 5)
=> akbkcCk-1 (by 6)
=>...=> akbkck (by 7)
结论：CSG、CFG、正规式能力递减
不过：能力越强的文法，其文法的设计和自动机的构造越困难
因此：语法分析仅用到CFG（除尤其指出，文法即指CFG ）
再考察L3：
3
自上而下语法分析 自上而下分析的一般措施
用推导的措施分析输入序列（记号流）：
对任何一种输入序列ω，从S开始进行最左推导，直到得到一种合法的句子或发现一种非法构造。
在推导的过程中，从左到右扫描输入序列，并试图用一切也许的措施，自上而下建立它的分析树。
自上而下分析是一种试探的过程，是反复使用不一样产生式寻求与输入序列匹配的过程。
4
自上而下分析的一般措施（续1）
用下述文法分析输入序列ω=cad：
S → cAd
A → ab
| a
问题：
若有A→αβ1|αβ2，(公共左因子)，则会虚假匹配和大量回溯；导致分析效率低、语义动作难以恢复、以及出错位置的汇报不确切等。
若有A→Aα，(左递归)，则死循环使分析无法进行下去。
重写文法：
消除左递归，以避免陷入死循环；
提取左因子，以避免回溯。
5
消除左递归
若文法G中的非终止符A，对某个文法符号序列α存在推导A=+>Aα，则称G是左递归的。若G中有形如A→Aα的产生式，则称该产生式对A直接左递归。 ■
<1> 消除文法的直接左递归
考虑： A→Aα|β 产生的语言：βα*
替代为：A→βA'
A'→αA'|ε 消除了一种直接左递归
6
<1> 消除文法的直接左递归(续1)
A→ Aα1|Aα2|...|Aαm|β1|β2|...|βn
其中αi非空，βj均不以A开始。然后用下述产生式替代A产生式：
若αi为空，则形成一种有环的A产生式
消除直接左递归
A → β1 A' |β2 A' | ...|βn A'
A'→ α1 A' | α2 A' | ... | αm A' |ε ■
输入 G中所有的A产生式(含直接左递归)
输出 等价的不含直接左递归的G'
措施 首先，整理A产生式为如下形式：
7
<1> 消除文法的直接左递归(续1)
：
E →TE' (1)
E'→+TE'|ε (2) (')
T →FT' (3) T'→*FT'|ε (4)
F →(E) |-F|id (5)..(7)
E→E+T|T
T→T*F|F ()
F→(E)|-F|id
替代： A→Aα|β
为： A →βA'
A'→αA'|ε
关键：将实际文法符号对应到A、α和β
详细到E产生式： E +T|T
A α β
8
<1> 消除文法的直接左递归(续2)
输入序列：id+id*id
改写的代价
E→E+T|T
T→T*F|F
F→(E)|-F|id
()
E →TE' (1)
E'→+TE'|ε (2)
T →FT' (3) T'→*FT'|ε (4)
F →(E) |-F|id (5)..(7)
(')
E→E+E|E*E
|(E)|-E|id
()
What a mess!
9
<2> 消除文法的左递归
文法：S→Aa|b A→Ac|Sd|ε
S左递归(但不是直接左递归)
由于：S=>Aa=>Sda
注意：若G产生句子的过程中出现A A的推导，则无法消除左递归
+
=>
关键思想：将不是直接左递归的非终止符右部展开到其他产生式中
for i in 2..n
loop for j in 1..i-1
loop
end loop;
end loop; ■
用Aj→δ1|δ2|...|δk的右部
替代每个形如Ai→Ajγ产生式中的Aj,
得到新产生式：Ai→δ1γ|δ2γ|...|δkγ;
消除Ai产生式中的直接左递归;
消除左递归
输入 无回路文法G
输出 无左递归的等价文法G'
措施 将非终止符合理排序：A1，A2，...，An;
10