当前位置：文档之家 › 编译 第三章 语法分析

编译 第三章 语法分析

  • 格式：ppt
  • 大小：681.00 KB
  • 文档页数：65

下载文档原格式

  / 65

合集下载

《编译原理》第3章

《编译原理》第3章

NFA到相应的DFA的构造的基本思路是： DFA的每 一个状态对应NFA的一组状态. DFA使用它的状 态去记录在NFA读入一个输入符号后可能达到的 所有状态.
NFA M所能接受的符号串的全体记为L(M)
结论：
上一个符号串集V是正规的，当且仅当存 在一个上的不确定的有穷自动机M，使得 V=L(M)。
DFA是NFA的特例.对每个NFA N一定存在一个DFA Ｍ，使得 L(M)=L(N)。对每个NFA N存在着与之 等价的DFA M。 有一种算法，将NFA转换成接受同样语言的DFA.这 种算法称为子集法. 与某一NFA等价的DFA不唯一.
0
1
S P
Z
{P} {}
{P}
{S,Z} {Z}
{P}
• δ为S * 到S的子集(2 S)的一种映射
• 从NFA的矩阵表示中可以看出，表项通常是一状态的集合， 而在DFA的矩阵表示中，表项是一个状态
∑*上的符号串t被NFA M接受:
• 对于Σ*中的任何一个串t，若存在一条从某一初态 结点到某一终态结点的道路，且这条道路上所有 弧的标记字依序连接成的串(不理采那些标记为ε 的弧)等于t，则称t可为NFA M所识别(读出或接 受)。 • 若M的某些结点既是初态结点又是终态结点；或 者存在一条从某个初态结点到某个终态结点的道 路,其上所有弧的标记均为ε，那么空字ε可为M所 接受。
其中： δ(S，0)={P}
δ(S，1)={S，Z} δ(Z，0)={P} δ(Z，1)={P} δ(P，1)={Z} • 状态图表示
1 1 S 0 0,1 Z
P
1
• 矩阵表示
状态 输入
δ(S，0)={P} δ(S，1)={S，Z} δ(Z，0)={P} δ(Z，1)={P} δ(P，1)={Z}

第3章 语法分析-编译原理及实践教程(第3版)-黄贤英-清华大学出版社

第3章 语法分析-编译原理及实践教程(第3版)-黄贤英-清华大学出版社
• 文法是被用来精确而无歧义地描述语言的句子的构成方式. • 文法描述语言的时候不考虑语言的含义。
3.2.1 文法的定义
例1：有如下规则
<句子><主语><谓语> <主语><代词>|<名词> <代词>我 <名词>大学生 <谓语><动词><直接宾语> <动词>是 <直接宾语><代词>|<名词>
(表示由…组成)
• 归约:推导的逆过程。
• 直接归约：直接推导的逆过程
几个概念的形式定义
• 直接推导: 如果αβ是文法 G=（Vn,Vt,P,S）
的产生式，γ和δ是Ｖ*中的任意符号，若有符号 串v,w满足： v=γαδ,w=γβδ,则说v直接产生w，(w是v的 直接推导)记作：v=>w 例：S01, 0S0=>0010(直接推导γ＝０,δ＝０) • 如果存在v=>w0=>w1=>w2...=>Wn=w(n>0)，则 称v推导出w（长度为n），记作v+=>w(至少一步) • 若有ｖ=>w或v=w，则记作v*=>w(0步或若干步)
一个非终结符号，β∈V*)
–上例中： G=（Vn,Vt,P,<句子>）
Vn=（<句子>，<主语>，<谓语>，<代词>，<动词>，
<名词>，<直接宾语>）
Vt= (我，是，大学生)
P=
<句子><主语><谓语>
<主语> <代词>|<名词>

编译原理及实现技术：7.语法分析__语法树、二义性文法

编译原理及实现技术：7.语法分析__语法树、二义性文法
一个现有文法是否为二义性文法。 常用的经验性判断:
SSS|a 可以推导出SSS串，必有二义性 SS+S 可以推导出S+S+S，必有二义 性
10
2.2 文法二义性的判定和利用
文法二义性的利用 对二义性文法进行修改，消除其二义性
会导致文法的复杂程度和符号数目迅速升 高。 可以利用二义性文法状态少，分析快的 特点，使用二义性文法，对具体问题加入 语义规则，约束其二义性即可。
16
若干历年考试题
设有一个文法G[S]: S->V V->T|ViT T->F|T+F F->V*|[
F+Fi[
句型F+Fi[的短语，简 单短语和句柄分别为： 首F,F+F, F+Fi[, [ 首F,[； 首F。
17
14
若干历年考试题
构造一个文法G，使 L(G)={anbmck|m=n+k,n≥1,m>1,k≥1}
G[S]: SAB AaAb| ab BbBc| bc
15
若干历年考试题
已知文法G[Z]: ZWV WaB | aW | a Bb | bB VbV | dD Dd | dD
判断文法G[Z]是否为二义性文法，如果是请举 例 句子abdd有两棵语法树。
语法树：设G是给定的语法，称满足下列条
件的树为G的一棵语法树： 1. 树的每个节点都标有G的一个语法符号，且根
节点标有初始符S。 2. 如果一个非叶节点A按从左到右顺序有n个儿子
节点B1、B2、…、Bn，则: AB1B2…Bn 一定是 G的一个产生式.
2
1.1 语法树的定义
例子：有文法
E
E E+T E T T T *F

编译原理第三章练习题答案

编译原理第三章练习题答案

编译原理第三章练习题答案编译原理第三章练习题答案编译原理是计算机科学中的重要课程之一，它研究的是将高级语言程序转化为机器语言的过程。

在编译原理的学习过程中，练习题是提高理解和应用能力的重要途径。

本文将为大家提供编译原理第三章的练习题答案，希望能够对大家的学习有所帮助。

1. 什么是词法分析？请简要描述词法分析的过程。

词法分析是编译过程中的第一个阶段，它的主要任务是将源程序中的字符序列划分为有意义的词素（token）序列。

词法分析的过程包括以下几个步骤：1）扫描：从源程序中读取字符序列，并将其转化为内部表示形式。

2）识别：根据预先定义的词法规则，将字符序列划分为不同的词素。

3）分类：将识别出的词素进行分类，如关键字、标识符、常量等。

4）输出：将分类后的词素输出给语法分析器进行进一步处理。

2. 什么是正则表达式？请给出一个简单的正则表达式示例。

正则表达式是一种用于描述字符串模式的工具，它由一系列字符和操作符组成。

正则表达式可以用于词法分析中的词法规则定义。

以下是一个简单的正则表达式示例：[a-z]+该正则表达式表示匹配一个或多个小写字母。

3. 请简要描述DFA和NFA的区别。

DFA（Deterministic Finite Automaton）和NFA（Nondeterministic Finite Automaton）是有限状态自动机的两种形式。

它们在词法分析中常用于构建词法分析器。

DFA是一种确定性有限状态自动机，它的状态转换是确定的，每个输入符号只能对应一个状态转换。

相比之下，NFA是一种非确定性有限状态自动机，它的状态转换是非确定的，每个输入符号可以对应多个状态转换。

4. 请简要描述词法分析器的实现过程。

词法分析器的实现过程包括以下几个步骤：1）定义词法规则：根据编程语言的语法规范，定义词法规则，如关键字、标识符、常量等。

2）构建正则表达式：根据词法规则，使用正则表达式描述不同类型的词素。

3）构建有限状态自动机：根据正则表达式，构建DFA或NFA来识别词素。

编译原理教程-课后习题答案第三章语法分析

编译原理教程-课后习题答案第三章语法分析

由 A′→ABl 得 FIRST(′l′) FOLLOW(B) ， 即 FOLLOW(B)={l}；
由 A→aA′ 得 FOLLOW(A) FOLLOW(A′) ， 即 FOLLOW(A′)={#,d}；
第三章 语法分析
由 B→dB′ 得 FOLLOW(B) FOLLOW(B′) ， 即 FOLLOW(B′)={l}。
第三章 语法分析
求得：
FIRST(A)={a}
FIRST(A′)={a, ε }
FIRST(B)={d}
FIRST(B′)={b, ε }
对文法开始符号A，有FOLLOW(A)={#}。
由 A′→ABl 得 FIRST(B)\{ ε }FOLLOW(A) ， 即 FOLLOW(A)={#,d}；
第三章 语法分析
3.9 考虑文法G[S]: S→(T) | a+S | a T→T,S | S
消除文法的左递归及提取公共左因子，然后对每 个非终结符写出不带回溯的递归子程序。
【解答】 消除文法G[S]的左递归： S→(T) | a+S | a T→ST′ T′→,ST′| ε
第三章 语法分析 提取公共左因子：
短语和最左素短语。 【解答】 (1) 句型(S, (a))的语法树如图3-5所示。
第三章 语法分析
S (L ) L ,S S (L )
S a
图3-5 句型(S,(a))的语法树
第三章 语法分析
(2) 由图3-5可知： 短语：S、a、(a)、S,(a)、(S,(a))； 直接短语：a、S； 句柄：S； 素短语：素短语可由图3-5中相邻终结符之间的优 先关系求得，即：
由图3-3可直接得到正规文法G[S]如下： G[S]：S→aA|bB A→aS|bC|b B→bS|aC|a C→bA|aB|ε

编译原理第三版课后习题答案

编译原理第三版课后习题答案

编译原理第三版课后习题答案编译原理是计算机科学中的一门重要课程，它研究的是如何将高级程序语言转换为机器语言的过程。

而《编译原理》第三版是目前被广泛采用的教材之一。

在学习过程中，课后习题是巩固知识、提高能力的重要环节。

本文将为读者提供《编译原理》第三版课后习题的答案，希望能够帮助读者更好地理解和掌握这门课程。

第一章：引论习题1.1：编译器和解释器有什么区别？答案：编译器将整个源程序转换为目标代码，然后一次性执行目标代码；而解释器则逐行解释源程序，并即时执行。

习题1.2：编译器的主要任务是什么？答案：编译器的主要任务是将高级程序语言转换为目标代码，包括词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等过程。

第二章：词法分析习题2.1：什么是词法分析？答案：词法分析是将源程序中的字符序列划分为有意义的词素（token）序列的过程。

习题2.2：请给出识别下列词素的正则表达式：（1）整数：[0-9]+（2）浮点数：[0-9]+\.[0-9]+（3）标识符：[a-zA-Z_][a-zA-Z_0-9]*第三章：语法分析习题3.1：什么是语法分析？答案：语法分析是将词法分析得到的词素序列转换为语法树的过程。

习题3.2：请给出下列文法的FIRST集和FOLLOW集：S -> aAbA -> cA | ε答案：FIRST(S) = {a}FIRST(A) = {c, ε}FOLLOW(S) = {$}FOLLOW(A) = {b}第四章：语义分析习题4.1：什么是语义分析？答案：语义分析是对源程序进行静态和动态语义检查的过程。

习题4.2：请给出下列文法的语义动作：S -> if E then S1 else S2答案：1. 计算E的值2. 如果E的值为真，则执行S1；否则执行S2。

第五章：中间代码生成习题5.1：什么是中间代码？答案：中间代码是一种介于源代码和目标代码之间的表示形式，它将源代码转换为一种更容易进行优化和转换的形式。

编译原理第三章语法分析


3.2 语言和文法
• 文法的优点
–文法给出了精确的，易于理解的语法说明 –自动产生高效的分析器
–可以给语言定义出层次结构
3.2 语言和文法
• 文法的优点
–文法给出了精确的，易于理解的语法说明 –自动产生高效的分析器
–可以给语言定义出层次结构
–以文法为基础的语言实现便于语言的修改
3.2 语言和文法
F id | (E)
3.2 语言和文法
E E+T|T TT* F|F F id | (E)
E T T T * F id F id
E E
T F
+
T F
T * F
id
*
F
id
id id * id * id 和 id + id * id 的分析树
id
3.2 语言和文法
3.2.5 消除二义性 stmt if expr then stmt | if expr then stmt else stmt | other • 句型：if expr then if expr then stmt else stmt
3.2 语言和文法
3.2.5 消除二义性 stmt if expr then stmt | if expr then stmt else stmt | other • 句型：if expr then if expr then stmt else stmt • 两个最左推导： stmt if expr then stmt if expr then if expr then stmt else stmt stmt if expr then stmt else stmt if expr then if expr then stmt else stmt

916073-编译原理原理与技术-第3章 语法分析


id
id
E E+E E E +E id E + E id id + E id id + id E
E +E
E
*
E id
id
id
3.2 语言和文法
• 文法的优点
–文法为语言给出了精确的、易于理解的语法规范 –自动产生高效的分析器 –可以给语言定义出层次结构 –以文法为基础的语言的实现便于语言的修改
FIRST(E) = FIRST(T) = FIRST(F) = { ( , id } FIRST(E ) = {+, } FRIST(T ) = {, } FOLLOW(E) = FOLLOW(E ) = { ), $} FOLLOW(T) = FOLLOW (T ) = {+, ), $} FOLLOW(F) = {+, , ), $}
id
+ term
term * factor
factor
id
id id + id id 分析树
3.2 语言和文法
3.2.5 消除二义性 stmt if expr then stmt
| if expr then stmt else stmt | other • 句型：if expr then if expr then stmt else stmt • 两个最左推导： stmt if expr then stmt if expr then if expr then stmt else stmt stmt if expr then stmt else stmt if expr then if expr then stmt else stmt
3.3 自上而下分析

编译原理第三章练习题答案

编译原理第三章练习题答案编译原理第三章练习题答案编译原理是计算机科学中的重要学科，它研究的是如何将高级语言代码转化为机器语言的过程。

在编译原理的学习过程中，练习题是不可或缺的一部分，通过完成练习题可以更好地理解和掌握编译原理的知识。

本文将为大家提供编译原理第三章练习题的答案，希望对大家的学习有所帮助。

1. 什么是语法分析？语法分析是编译器中的一个重要模块，它的主要任务是根据给定的语法规则，对输入的源代码进行分析和解释。

语法分析器会根据语法规则构建一个语法树，用于表示源代码的结构和含义。

常用的语法分析方法有递归下降法、LL(1)分析法和LR分析法等。

2. 什么是LL(1)文法？LL(1)文法是一种特殊的上下文无关文法，它具有以下两个特点：(1) 对于任何一个句子，最左推导和最右推导是唯一的。

(2) 在预测分析过程中，只需要向前看一个输入符号就可以确定所采用的产生式。

LL(1)文法是一种常用的文法形式，它适用于递归下降法和LL(1)分析法。

3. 什么是FIRST集合和FOLLOW集合？FIRST集合是指对于一个文法符号，它能够推导出的终结符号的集合。

FOLLOW 集合是指在一个句型中，某个非终结符号的后继终结符号的集合。

计算FIRST集合和FOLLOW集合可以帮助我们进行语法分析，特别是LL(1)分析。

4. 什么是递归下降语法分析法？递归下降语法分析法是一种基于产生式的自顶向下的语法分析方法。

它的基本思想是从文法的开始符号开始，递归地根据产生式进行分析，直到推导出输入符号串或发现错误。

递归下降语法分析法的实现比较简单，但对于某些文法可能会出现回溯现象，影响分析效率。

5. 什么是LR分析法？LR分析法是一种自底向上的语法分析方法，它的基本思想是从输入符号串开始，逐步构建语法树，直到推导出文法的开始符号。

LR分析法具有较好的分析效率和广泛的适用性，常用的LR分析方法有LR(0)、SLR(1)、LR(1)和LALR(1)等。

编译原理(3)语法_2(推导与语法树)

3、在一棵语法树生长 过程中的任何时刻， 所有那些没有后代的 树叶结点自左至右排 列起来就是一个句型。
图3-4 句子i+i*i的语法树
4、一棵已经完成的语法树无法判断是来自于最左推导还 是最右推导，而使用文法规则的推导过程是有先后之分的。 如果坚持使用最左(或最右)推导，那么一棵语法树就完全 等价于一个最左(或最右)推导
•
棵不同的语法树:
最左推导1
E E E i E i E * E ii* E ii*i
最左推导2
E E * E E E * E i E * E i i* E i i*i
3.2

推导与语法树
3.2.2 语法树与二义性
–
3、语法的二义性
3.2

推导与语法树
3.2.2 语法树与二义性
–
2、子树与短语
•
语法树某个结点连同它的所有后代组成了一棵子树。只含有 单层分枝的子树称为简单子树。 子树与短语的关系十分密切，根据子树的概念，句型的短语、 直接短语、句柄和素短语的直观解释如下：
•
(1) 短语：子树的末端结点(即树叶)
组成的符号串是相对于子树根的短语； (2) 直接短语：简单子树的末端结点 组成的符号串是相对于简单子树根的 直接短语 b
都是指句型中的哪些符号串能够构成短语、直接短语、句
柄。脱离句型，谈论三者是无意义的。
例5.2 文法G E → T | E +T T → F | T * F F → i |（E） i1*i2+i3 是文法G的一个句型吗？ 如果是，求出其句柄。
3.2

推导与语法树
3.2.1 推导与短语
–
4、素短语
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

三、错误恢复策略
(1)紧急方式恢复：发现错误时，分析器每次抛弃一个输入记号， 直至输入记号属于某个指定的同步记号集合为止。 同步记号一般是定界符，如分号或end。 优点：方法简单，不会陷入死循环。 适用于一个语句中很少出现多个错误的情况。 (2)短语级恢复：发现错误时，分析器对剩余输入作局部纠正， 用可以使分析器继续分析的输入串来代替剩余输入的前缀。 如：用分号代替逗号、删除多余的分号、插入遗漏的分号。 这种替换可用于纠正任何输入串，已经用于几个错误修复编 译器，首先是用于自上而下的分析方法。它的主要缺点是很 难应付实际错误出现在诊断点以前的情况。 (3)出错产生式：如果对经常遇到的错误了解得很清楚 ，就可以 扩充语言的文法，增加产生错误结构的产生式，用此扩充的 方法来构造分析器。 (4)全局纠正： 在处理不正确的输入串时，作尽可能少的修改。 5
T
T→F|T*F F→(E)| i
E为表达式, T 为项, F 为因子F FT Nhomakorabea*
i
F i
该文法对于句子i * i + i的各种 推导,对应的语法树是唯一的. 16
i
1、文法的优点： 文法给出了精确的、易于理解的语言语法说明。 某些文法类可以自动产生高效的分析器，分析器的构造过程 可以揭示出语法的二义性和其他难于分析的结构。 设计的漂亮的文法把结构加于程序设计语言，这些结构对于 把源程序翻译成为正确的目标代码和错误诊断都是很有用的 语言也是逐渐完善的，需要补充新的结构和完成附加的任务。 如果存在以文法为基础的语言的实现，这些新结构的加入就 更方便。 但是不是所有的语言都可以用上下文无关文法来描述， 例如：我们变量的使用就要求先定义后使用，后面的使用就 的根据前面的类型和属性来决定。即：程序语言也有一定的 语言环境。因此我们强调语法分析器的输出结果。 本章介绍语法分析，是分析语法结构，使用文法；而前 一节词法分析，是分析我们的词法规则，使用正规式；他们 有什么区别、联系、相似之处。 17
例如：考虑一个文法G1:





S→ bA A→ β |a β →aA 它定义了一个什么样的语言呢？ S是开始符号，是非终结符 A是非终结符 β是终结符与非终结符组成的字符串 b是终结符 a是终结符 结论：S→ baa*
10
3 文法 G 与语言L(G)的关系及术语
从文法初始符开始,反复用产生式右部替换左部的非终结符, 直到推出的符号串全部由终结符组成.得到G所定义的各种句子. 例如:E=>E+E=>E*E +E=>i * E + E=> i * i + E => i * i + i 定义: 若αBβ,经产生式 B→λ替换后得到 αλβ,称αBβ直接 推出αλβ.{α , λ,β ∈(VT ∪ VN) *},用=>表示直接推出. 若存在α1=> α2 => α3........=> αn ,称α1可推出αn; + α1=> αn表示经一步或若干步α1可推出αn. * α 表示经零步或若干步α 可推出α . α1=> n 1 n * {α ∈(VT ∪ VN) *}, 则称 定义:设S 是G的开始符号,若 S=>α,
3.2 上下文无关文法
文法：是描述语言的语法结构的形式规则(即语法规则) 形式描述：用一组数学符号和规则来描述语言的方式。 形式语言：形式描述所用的数学符号和规则。 形式：指仅考虑数学符号间的推演,而不涉及符号的具体含义。 上下文无关文法是这样一种文法: 它定义的语法单位,独立 于该语法单位可能出现的环境,不必考虑上下文关系. 自然语言不是上下文无关文法; 程序语言是上下文无关文法. 程序设计语言的许多结构包含固有的递归性，可用上下文 无关文法定义。 例：如果S1和S2是语句，E是表达式，则 “if E then S1 else S2”是语句。 使用语法变量stmt表示语句类，用expr表示表达式类，上述语 句可用文法产生式方便地表示为： stmt→if expr then stmt else stmt 6
二、语法错误的处理
程序的错误有各种不同的性质。例如，错误可能是： (1)詞法错误，如标识符、关键字或算符的拼写错误 (2)语法错误，如算术表达式的括号不配对 (3)语义错误，如算符作用于不相容的运算对象 (4)逻辑错误，如无穷的递归调用。 大多数错误的诊断和恢复集中在语法分析阶段，原因如下： (1)大多数错误是语法错误 (2)诊断语法错误比诊断语义错误和逻辑错误容易得多。 分析器出错处理的基本目标是： (1)清楚而准确地报告错误的出现； (2)迅速从每个错误中恢复过来，以便诊断后面的错误 (3)不应使正确程序的处理速度降低太多。 4
2
3.1
分析器的作用
一、语法分析的任务: 把单词符号作为基本单位,根据文法,分析源程序 (字 符串)是否为合法的程序. 同时报告语法错误并进行错误的恢复，使后面的分析 能够进行下去。
源程序 词法 分析器 记号 分析器 取下一个 记号 分析树 前端的 中间表示 其余部分
3
符号表 分析器在编译器模型中的位置
α是 G的一个句型;若 α ∈VT *,则称α是 G的一个句子. 如果两个文法产生同样的语言，则这两个文法等价。
11
例如： E=>E+E=>E*E +E=>i * E + E=> i * i + E => i * i + i


E是我们的开始符号，也是非终结符 +、-、*、/是终结符 i是终结符 E+E、E*E +E、i * E + E、 i * i + E是句型 i*i+i是句子 E=>E+E、 E+E =>E*E +E、 E*E +E =>i * E + E、 i * E + E => i * i + E是经一步推导出----直接推导 E => i * i + i是经多步推导出-----可推导出
1. 上下文无关文法定义
7
上下文无关文法 G 是一个四元组: G =(VT,VN,S,P) VT ： 是一个非空有限集,每个元素称为终结符. 程序设计语言的文法中记号是终结符的同义词。 例如：if,then,else,while,do,等都是终结符。 VN：是一个非空有限集,每个元素为非终结符,代表了一种 语法单位. 且 VT ∩ VN=φ. 例如:表达式,短语,语句等。 S: 是一个非终结符，称为开始符号,S ∈ VN. S 是文法G 的最高层次的语法单位. 在程序语言中, S代表了程序这一语法概念. P: 是产生式的有限集合。一条产生式定义了一个非终结 符，产生式形式如下: A→ α (A∈ VN , α∈ (VT ∪ VN ) * ) 称A定义为α . (→ 有时也会用::=代替) α∈ (VT | VN ) *
定义: 若文法 G 的某个句型存在两个不同的语法树表示,称该文法 是二义文法. 因此,文法 E 是二义文法. 二义性导致了i * i + i 的两种不同运 算结果: (i*i)+i 以及 i*(i+i). E 编译中应避免二义文法. E 文法的 二义性是因为没有规定*,+ 运算符的优 E + T 先顺序,改进 E 后,得到: E→T|E+T
例：文法({id,+,-,*,/,↑,(,)},{expr,op},expr,P) 定义了简单的算术表达式，P是由下列产生式组成的有 限集合： expr→expr op expr expr→(expr) expr→-expr expr→id op→+ op→op→* op→/ op→↑
3. 文法的表式及产生的语言
例如 文法：S→(S)S|ε 推导我们的文法产生式，每一次推导得到的终结符为（） 或则ε ，（）成对出现，而ε是空串，所以此文法描述的语 言是所有的配对括号组合。 例如 文法：S →if expr then stml A A →else B|ε B →S|stml stml →S| stml |ε 推导文法产生式，可以得到我们的if语句的语法结构， 包括if的嵌套结构，描述所有的if语句。 例如 文法：S →while expr do { stml } stml →stml |ε 推导文法产生式，得到该文法描述的是我们所有的 while循环语句。 19
例如 设expr和term为非终结符，用以表式不同的优先级，终 结符为id、括号、运算符等，facter为产生表达式的基本单 位。则： 文法一 facter →id|(expr) term →term*facter|term/facter|facter expr →expr+term|expr-term|term 这个表达式文法是无二义性的，句子id+id+id和id+id*id的分 析树如下： expr expr expr + term expr + term facter expr + term term term * facter term facter id facter facter id facter id id id 20 id
第三章 语法分析
语法分析概述
自下而上分析法 自上而下分析法
语法分析方法
自下而上是指: 根据文法,对输入字串进行归约,若能正确地归约
为文法的初始符号,则表示输入字串是合法的. 典型方法是算符优先分析法.
自上而下是指: 从文法的初始符号进行推导,若能推导出与输入
字串相同的句子,则表示输入字串是合法的. 典型方法是递归下降分析法.

8
2 文法的几点约定
a) 若 A→ α1 A→ α2
则简写为: A→ α1|α2|...... |αk
9