递归文法
A→Ba B→Ab
间接递归文法
4.3.1 左递归的消除

直接消除见诸于产生式中的左递归：假 定关于非终结符P的规则为
P→P | 其中不以P开头。
我们可以把P的规则等价地改写为如下的 非直接左递归形式： P→P 左递归变 P→P| 右递归
一般而言，假定P关于的全部产生式是 P→P1 | P2 | … | Pm | 1 | 2|…|n 其中，每个都不等于，每个都不以P开头
<句子> => <主语><谓语><宾语>
=> <代词><谓语><宾语> => he <动词><宾语>
=> he has <宾语>
=> he has <冠词><名词>
<句子> ::= <主语><谓语><宾语> <主语> ::= <代词> <代词> ::= he <冠词> ::= a <名词> ::= pen <谓语> ::= <动词> <动词> ::= has <宾语> ::= <冠词><名词> <名词> ::= pen
文法和语法分析
高级语言的语法结构适合使用 上下文无关文法描述。
文法及语言的形式定义
文法是对语言结构的定义与描述（或 称为“语法”），即用适当条数的规 则把语言的全部句子描述出来。 文法是以有穷的集合刻划无穷的集合 的工具。
文法

文法能清晰地描述程序设计语言的语法构 成易于理解。
文法能自动地构造有效的语法分析器，检 查源程序是否符合语言规定的语法形式。 文法定义可以了解程序设计语言的结构， 有利于将源程序转化为目标代码，以及检 查出语法错误。 基于文法实现的语言易于扩展。
S ·
a c A d b
完成进一步推导Acd 检查,c-c匹配,b-d不匹配(失败) 但是还不能冒然宣布α L(G[S]) 4.回溯 即砍掉A的子树 改选A的第二右部 Ac 检查 c-c匹配 b-b匹配
S ·
a A b α=acb G[S]: S→aAb A→cd|c
建立语法树,末端结点为acb与输入acb相匹配, c 建立了推导序列 SaAbacb ∴acbL(G[S])
2. 如果语言是无穷的，描述语言有两种途径：

制定有限条规则，用于产生所要描述的语言的 全部句子（可无限多），这些规则构成了该语
言的文法。

设计一种装置（算法或过程），它以某字母表
上的符号串为输入，判别该符号串是否为所描
述语言的句子。此装置称为自动机。
语言概述
程序设计语言——形式化的内容提取
程序设计语言(Programming
基本思想：从输入串开始，逐步进行“
归
约”，直到文法的开始符号。即从树末端
开始，构造语法树。所谓归约，是指根据 文法的产生式规则，把产生式的右部替换 成左部符号。 算符优先分析法：按照算符的优先关系和 结合性质进行语法分析。适合分析表达式。 LR分析法：规范归约
G(E)： E i| E+E | E-E | E*E | E/E | (E) i*i+i E*i+i E*E+i E+i E+E E E E + E
P→1P | 2P |… | mP |

例如文法G(S): S→Qc|c Q→Rb|b R→Sa|a
SQcRbcSabc
(4.3)
虽没有直接左递归，但S、Q、R都是左递归的
一个文法消除左递归的条件： 不含以为右部的产生式 不含回路。
P P


消除左递归的算法:
1. 把文法G的所有非终结符按任一种顺序排列成P1， P2，…，Pn；按此顺序执行； 2. FOR i:=1 TO n DO
=> he has a <名词>
=> he has a pen
上下文无关文法的形式定义
一个上下文无关文法G是一个四元式 G=(VT，VN，S，P)，其中
VT：终结符集合(非空) VN：非终结符集合(非空)，且VT S：文法的开始符号，SVN P：产生式集合(有限)，每个产生式形式为
4.
4.3 LL(1)分析法

构造不带回溯的自上而下分析算法
要消除文法的左递归性 克服回溯
递归文法
1.递归规则：产生式右部有与左部相同的符号
左递归规则：A→A… 右递归规则：A→…A 自嵌入递归规则：A→…A…
递归文法
2.递归文法：含有递归规则的文法，为 直接递归文法
G[S]： S→L|SL|SD L→a|b|…|z D→0|1|…|9
计算机系统间、人机间通讯工具 严格的语法(Grammar)、语义
(Semantics) ——易于形式化：严格 语言是用来交换信息的工具——功能性描述
什么是语言
语言
单词(Token)：满足一定规则字符(Character)串
句子(Sentence)：满足一定规则单词序列
语言(Language)：满足一定条件的句子集合
V N=
P， PVN， (VT VN)* 开始符S至少必须在某个产生式的左部出现一 次。

例，定义只含+，*的算术表达式的文法 G=<{i，+，*，(，)}，{E}，E， P>， 其 中，P由下列产生式组成： Ei E E+E E E*E E (E)
4.1 语法分析器的功能
【例4.1】 α=acb G[S]: S→aAb A→cd|c
分析过程是设法建立一 棵语法树,使语法树的末端结 点与给定符号串相匹配.
1.开始:令S为根结点 2.用S的右部,符号串去匹配输入串
S S ·
·
完成一步推导SaAb a A 检查 a-a匹配 A是非终结符,将匹配任务交给A
b
3.选用A的右部符号串匹配输入串 A有两个右部,选第一个
E i
* E
i
i
语法分析的方法： 自上而下分析法(Top-down)

基本思想：它从文法的开配"的推
导。
递归下降分析法 预测分析程序
优点：直观、简单和宜于手工实现。
4.2
自顶向下分析法
4.2.1 自顶向下分析的一般过程
从S出发采用最左推导，试图逐步推出输入串 α,αL(G[S])? S作为语法树的根，试图自上而下地为α构造一棵语法 树 •若叶结点从左向右排列恰好α，则表示α是文法的 句子，而这棵语法树就是句子α的语法结构 •若构造不出语法树，则α不是文法的句子

产生式集合P = {句子 → 主语谓语 ，……}
开始符号S = 句子
句子的推导___根据规则

由规则推导句子：有了一组规则之 后，可以按照一定的方式用它们去 推导或产生句子。

推导方法：从一个要识别的符号开 始推导，即用相应产生式的右部来 替代产生式的左部，每次仅用一条 规则去进行推导。
左递归文法会使自顶向下分析法陷入死循环
如果文法具有间接左递归，则也将发生上述问题，只不过循 环的圈子兜的更大
要实行自顶向下分析，必须要消除文法的左递归
3.
在上述自上而下分析过程中，当一个非终 结符用某一候选式匹配成功时，这种成功 可能只是暂时的。由于这种虚假现象，我 们需要采用更复杂的回溯。 当最终报告分析不成功时，我们难于知道 输入串中出错的确切位置。
BEGIN FOR j:=1 TO i-1 DO


根据语言的语法规则 ，分析源程序的语法结 构，即分析如何由这些单词组成各种语法范畴 (如下标变量、各种表达式、各种语句、程序段 或分程序，乃至整个源程序等等)，并在分析过 程中，对源程序进行语法检查。

作为语法分析程序的输出，可以有多种不 同的形式。在下面的讨论中，为简便起见， 我们假定语法分析程序的输出，是用某种 方法表示的语法树

那么，消除P的直接左递归性就是把这些规 则改写成： P→1P | 2P | … | nP P→1P | 2P |… | mP |
左递归变 右递归

例 文法G(E): E→E＋T | T T→T*F | F F→(E) | i
经消去直接左递归后变成： E→TE (4.2) E→+TE | P→P1 | P2 | … | Pm | 1 | T→FT 2|…|n T→*FT | P→1P | 2P | … | nP F→(E) | i
Language)：组
成程序的所有语句的集合
程序(Program)：满足语法规则的语句序列 语句(Sentence) 单词(Token)
：满足语法规则的单词序列
：满足词法规则的字符串
文法和语法分析
正规式的局限性：不能用于描述配 对或嵌套的结构

固定次数的重复或者没有 指定次数的重复 例2：{wcw | w是a和b的串} 适合描述和识别语言 的单词符号； 仅能表示给定结构的 例1：配对括号串的集合
语言是字和组合字的规则——结构性描述
例：去吃我们中汉堡午
中午我们去吃汉堡
如何描述一种语言？
1. 如果语言是有穷的（只含有有穷多
个句子），可以通过枚举法将语言所有
的句子列出表示。

例如，只含两个句子的语言：{“I am
a teacher”, “You are students”};
如何描述一种语言？
语法分析的任务是分析一个文法的句子 结构。 语法分析器的功能：按照文法的产生式 (语言的语法规则)，识别输入符号串是 否为一个句子(合式程序)。