编译原理-语言与自动机.ppt

上次课程内容回顾
一、二义性与二义性的消除
造成二义性的原因－文法符号缺乏明确的优先级和结合性
消除二义性的方法：
改写二义文法为无二义文法
为文法符号规定优先级和结合性
改变语言的结构或书写方式
二、语言与文法的分类
正规式、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。 ■
若文法G=(N，T，P，S)的每个产生式α→β中，均有α∈(N∪T)*，且至少含有一个非终结符，β∈(N∪T)*，则称G为0型文法。
2
形式语言与自动机简介（续1）
文法、语言与自动机
文 法
语 言
自 动 机
短语文法 (0型)
短语结构语言
图灵机
CSG (1型)
CSL
线性界线自动机
CFG (2型)
CFL
下推自动机
正规文法 (3型)
正规集
有限自动机
3
形式语言与自动机简介（续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：
4
自上而下语法分析 自上而下分析的一般方法
用推导的方法分析输入序列（记号流）：
对任何一个输入序列ω，从S开始进行最左推导，直到得到一个合法的句子或发现一个非法结构。
在推导的过程中，从左到右扫描输入序列，并试图用一切可能的方法，自上而下建立它的分析树。
自上而下分析是一种试探的过程，是反复使用不同产生式谋求与输入序列匹配的过程。
5
自上而下分析的一般方法（续1）
用下述文法分析输入序列ω=cad：
S → cAd
A → ab
| a
问题：
若有A→αβ1|αβ2，(公共左因子)，则会虚假匹配和大量回溯；造成分析效率低、语义动作难以恢复、以及出错位置的报告不确切等。
若有A→Aα，(左递归)，则死循环使分析无法进行下去。
重写文法：
消除左递归，以避免陷入死循环；
提取左因子，以避免回溯。
6
消除左递归
若文法G中的非终结符A，对某个文法符号序列α存在推导A=+>Aα，则称G是左递归的。若G中有形如A→Aα的产生式，则称该产生式对A直接左递归。 ■
<1> 消除文法的直接左递归
考虑： A→Aα|β 产生的语言：βα*
替换为：A→βA'
A'→αA'|ε 消除了一个直接左递归
7
<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产生式为如下形式：
8
<1> 消除文法的直接左递归(续2)
：
E →TE' (1)
E'→+TE'