编译原理ch3 语法分析

字数统计: 2.3k字   |   阅读时长: 9分

本文主要内容是自顶向下分析概述、文法转换、LL（1）文法等。

语法分析主要任务

语法分析器(parser)从词法分析器输出的token序列中识别出各类短语，并构造语法分析树(parse tree)

赋值语句分析树

1
2
position = initial + rate * 60 ;
<id, position> <=> <id,initial> <+> <id, rate> <*> <num,60> <;>

赋值

变量声明语句的分析树

1
2
3
4
5
6
7
文法：
<D> → <T> <IDS>;
<T> → int | real | char | bool
<IDS> → id | <IDS>, id

输入：
int a , b , c ;

声明

1
2
3
4
解释
D -> Declaration
T -> Type
IDS -> Identifier Sequence

自顶向下的分析

从分析树的顶部（根节点）向底部（叶节点）方向构造分析树,可以看成是从文法开始符号S推导出词串w的过程。

举例

文法
① E → E + E
② E → E * E
③ E → ( E )
④ E → id
输入
id + ( id + id )

推导过程： 

1
2
3
4
5
6
E -> E + E
-> E + ( E )
-> E + ( E + E )
-> E + ( id + E )
-> id + ( id + E )
-> id + ( id + id )

声明

思考

每一步推导中，都需要做两个选择：

  1. 替换当前句型中的哪个非终结符
  2. 用该非终结符的哪个候选式进行替换

最左推导

在最左推导中，总是选择每个句型的最左非终结符进行替换
声明

最右推导

在最右推导中，总是选择每个句型的最右非终结符进行替换
声明
在自底向上的分析中，总是采用最左归约的方式，因此把最左归约称为规范归约，而最右推导相应地称为规范推导

最左推导和最右推导的唯一性

声明

自顶向下的语法分析采用最左推导方式

分析器从左向右扫描，因此自顶向下的语法分析采用最左推导方式

  1. 总是选择每个句型的最左非终结符进行替换
  2. 根据输入流中的下一个终结符，选择最左非终结符的一个候选式
    声明

自顶向下语法分析的通用形式

递归下降分析 (Recursive-Descent Parsing)

  1. 由一组过程组成，每个过程对应一个非终结符
  2. 从文法开始符号S对应的过程开始，其中递归调用文法中其它非终结符对应的过程。如果S对应过程体恰好扫描了整个输入串，则成功完成语法分析 
1
2
3
4
5
6
7
8
9
10
void A( ) {
    选择一个A产生式， A →X1 X2 … Xk ；
    for ( i = 1 to k ) {
    	if ( Xi是一个非终结符号)
    		调用过程 Xi ( ) ;
    	else if ( Xi 等于当前的输入符号a)
    		读入下一个输入符号;
    	else /* 发生了一个错误 */ ;
    }
}

可能需要回溯(backtracking)，导致效率较低

预测分析 (Predictive Parsing)

  • 预测分析是递归下降分析技术的一个特例，通过在输入中向前看固定个数（通常是一个） 符号来选择正确的A-产生式。

  • 可以对某些文法构造出向前看k个输入符号的预测分析器，该类文法有时也称为LL(k) 文法类

  • 预测分析不需要回溯，是一种确定的自顶向下分析方法

文法转换

并非所有文法均适合自顶向下分析

回溯问题

1
2
3
4
5
6
7
文法G
S → aAd | aBe
A → c
B → b

输入
a b c

同一非终结符(S)的多个候选式(aAd aBe)存在共同前缀(a)，将导致回溯现象

无限循环问题

1
2
3
4
5
6
7
文法G
E → E + T | E – T | T
T → T * F | T / F | F
F → ( E ) | id

输入
id + id * id
1
2
3
4
5
推导过程如下，存在问题。
E → E + T
→ E + T + T + T
→ E + T + T
→ …

  • 含有A→Aα形式产生式的文法称为是直接左递归的(immediate left recursive)

  • 如果一个文法中有一个非终结符A使得对某个串α存在一个推导A→+Aα （A推出以A开头的串），那么这个文法就是左递归的

  • 经过两步或两步以上推导产生的左递归称为是间接左递归的

左递归文法会使递归下降分析器陷入无限循环

消除直接左递归

解决方法

1
2
3
4
5
6
7
8
9
10
11
12
A → Aα | β(α≠ ε, β不以A开头)

推导过程：
A → Aα
→ Aαα
→ Aααα
…
→ Aα…α
→ βα…α

r=βα*

1
2
3
4
5
6
7
8
9
10
A → β A′
A′ → α A′｜ε

A′推导过程：
A′ → αA′
→ ααA′
→ αααA′
…
→ α…αA′
→ α…α

事实上，这种消除过程就是把左递归转换成了右递归

练习

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
文法：
E → E + T｜T
转换：
E→ T E′
E′ → + T E′ |ε

文法：
T → T * F｜F
转换：
T→ F T ′
T ′→* F T ′ ｜ε

文法：
F → ( E )｜id
转换：
F→ ( E )｜id

消除直接左递归的一般形式

1
2
3
4
5
6
7
A → Aα1 | Aα2 | … | Aαn | β1 | β2 | … | βm
(αi ≠ ε, βj不以A开头)

转换后：

A → β1 A′ | β2 A′ | … | βm A′
A′ → α1 A′ | α2 A′ | … | αn A′ | ε

消除左递归是要付出代价的——引进了一些非终结符（A′）和ε_产生式

消除间接左递归

1
2
3
4
5
6
7
8
9
10
11
12
13
S → A a | b
A → A c | S d | ε
存在间接左递归
S → Aa
→ Sda

消除方法：
将S的定义代入A-产生式，得：
A → A c | A a d | b d | ε

消除A-产生式的直接左递归，得：
A → b d A’ | A’
A’ → c A’ | a d A’ | ε

消除左递归算法

输入：不含循环推导（即形如A → + A的推导）和ε-产生式的文法G
输出：等价的无左递归文法 

1
2
3
4
5
6
7
8
1)按照某个顺序将非终结符号排序为A1， A2， … ， An .
2) for ( 从1到n的每个i ) {
3) 		for ( 从1到i -1的每个i ) {
4) 			将每个形如Ai → Aj γ的产生式替换为产生式组 Ai → δ1γ ∣ δ2γ ∣ … ∣ δkγ ，
		其中Aj → δ1 ∣ δ2 ∣ … ∣ δk ，是所有的 Aj 产生式
5) 		}
6) 		消除 Ai 产生式之间的立即左递归
7) }

提取左公因子(Left Factoring )

举例

1
2
3
4
5
6
7
8
9
10
文法G
S → aAd | aBe
A → c
B → b
替换为：
文法G'
S → a S'
S' → Ad | Be
A → c
B → b

通过改写产生式来推迟决定，等读入了足够多的输入，获得足够信息后再做出正确的选择

提取左公因子算法

输入：文法G
输出：等价的提取了左公因子的文法 

1
2
3
4
5
6
对于每个非终结符A，找出它的两个或多个选项之间的最长公共前缀α。 如果α ≠ ε，即存在一个非平凡的( nontrivial )公共前缀，那么将所有A-产生式
A → α β1 | α β2 | … | α βn | γ1 | γ2 | … | γm
替换为
A → α A' | γ1 | γ2 | … | γm
A' → β1 | β2 | … | βn
其中， γi 表示所有不以α开头的产生式体； A'是一个新的非终结符。不断应用这个转换，直到每个非终结符的任意两个产生式体都没有公共前缀为止

LL（1）文法

S文法

简单的确定性文法

  1. 每个产生式的右部都以终结符开始
  2. 同一非终结符的各个候选式的首终结符都不同

S_文法不含ε产生式

预测分析法的工作过程 ：

从文法开始符号出发，在每一步推导过程中根据当前句型的最左非终结符A和当前输入符号a，选择正确的A-产生式。为保证分析的确定性，选出的候选式必须是唯一的。

什么时候使用ε产生式？

如果当前某非终结符A与当前输入符a不匹配时，若存在A→ε，可以通过检查a是否可以出现在 A的后面，来决定是否使用产生式 A→ε（若文法中无 A→ε ，则应报错）

非终结符的后继符号集

定义

可能在某个句型中紧跟在非终结符A后边的终结符a的集合，记为FOLLOW(A)
FOLLOW(A)={a| S -》 * αAaβ, a∈VT， α,β∈(VT∪VN)*}

举例

1
2
3
4
5
6
7
8
9
(1) S → aBC
(2) B → bC
(3) B → dB
(4) B → ε
(5) C → c
(6) C → a

FOLLOW(B) = {a,c}

如果 A是某个句型的的最右符号，则将结束符“$”添加到FOLLOW(A)中。

串首终结符

定义

串首第一个符号，并且是终结符，简称首终结符。
给定一个文法符号串α， α的串首终结符集FIRST(α)被定义为可以从α推导出的所有串首终结符构成的集合。

如果α -》 * ε，那么ε也在FIRST(α)中。 

1
2
3
对于任意α∈(VT∪VN)+, FIRST(α)={ a | α -》 *aβ， a∈ VT， β∈(VT ∪ VN)*}；

如果 α -》 * ε， 那么ε ∈ FIRST(α)

LL(1)文法

  • 第一个“ L”表示从左向右扫描输入
  • 第二个“ L”表示产生最左推导
  • “ 1”表示在每一步中只需要向前看一个输入符号来决定语法分析动作

文法G是LL(1)的，当且仅当G的任意两个具有相同左部的产生式A → α | β 满足下面的条件：

  1. 不存在终结符a使得α 和β都能够推导出以a开头的串 (理解：α 和β不能都推出以终结符a开头的串)

  2. α 和β至多有一个能推导出 ε

  3. 1
    2
    如果 β -》 *ε，则 FIRST (α)∩FOLLOW(A) =Φ；
    如果 α -》 *ε，则 FIRST (β)∩FOLLOW(A) =Φ；
赏

谢谢你请我吃糖果

支付宝
微信

扫一扫，分享到微信

微信分享二维码
-->

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

日日行，不怕千万里； <br><br> 常常做，不怕千万事。 <br><br> INTJ <br><br> 天真认生，请多指教。