编译原理 | Colommar Blog

Ch1 概述

原目录：编译原理

1.1 语言处理器

处理器	Compilers	Interpreters
执行模式	将源代码翻译成目标语言编写的程序后再执行输入,产生输出	不翻译,直接利用输入执行源程序
执行速度	远快于解释器	较慢
错误诊断	弱于解释器	更好,因为逐个语句地执行源程序
语言代表		Python
优点	经过“翻译”后，目标程序的执行速度更快	逐句执行，对源程序的错误诊断效果更好更好的支持多平台，只需要不同平台的不同解释器就能跨平台的运行源程序

混合编译的语言: Java

Java程序先被compiled成字节码(bytecode)作为中间形式
之后由不同平台的JVM将其interpret,直接根据输入产生输出,从而保证了Java程序可以跨平台执行

1.2 编译器的结构

编译主要分为7个阶段

词法分析

Lexical analysis,也称为scanning

输入: 源程序的字符流

转换: 有意义的词法单元(token),形式如下:<token-name, attribute-value>

语法分析

Syntax analysis,也称parsing

输入: token

输出: 分析树parse tree或语法树syntax tree

语义分析

Semantic analysis

输入: 语法树和符号表中信息

执行:

类型检查: 比如数组下标一定为int
类型转换: 比如int和float一起运算,int->float

👉右图即为检查过程

中间代码生成

Intermediate code generation

输入: 通过了syntax analysis和semantic analysis的源程序

输出: 明确的低级或类机器码的表示

👉右图以三地址码为例,每条指令最多三个运算分量,一个运算符

(机器无关)优化

machine-independent optimization

机器无关的代码优化,只和源码有关

输入: 中间代码

输出: 优化后代码

👉右图进行常数折叠(机器无关)

代码生成

Code generation

输入: 中间代码

执行: 例如为变量选择寄存器或内存位置

输出: 可完成任务的机器指令(目标代码)

(机器相关)优化

machine-dependent optimization

机器相关的代码优化,和目标代码有关

输入: 目标代码

输出: 优化后代码

👉右图进行指令优化

1.3 其余概念

前端/后端

根据当前操作的依赖,可把编译过程分为前后端

前端

后端

取决于"源代码",包括:

词法分析
语法分析
语义分析
中间代码生成
机器无关优化

取决于"目标语言",包括:

代码生成
机器相关优化

前后端中介: "中间代码"

符号表

记录变量名和与之相关信息,如"类型,作用域,参数类型,参数数量,传参方法,返回类型"

遍(Pass)

将源码生成最终目标代码前的多次重复称为遍(pass),多个编译步骤组合成一遍,每遍一个输入文件,一个输出文件,大多数编译器使用不只一遍(比如前端步骤可以组合为一趟,后端步骤组合为一遍)

Ch3 词法分析

原目录：编译原理

查看语雀原文

词法分析器:从源码中读取字符,转换成逻辑单元/词法单元(tokens)

3.1 词法单元,词素,模式

Token	词法单元<name,value>
Lexeme	词素,源程序的字符序列,可用于匹配
Pattern	模式,描述一个Token的Lexeme可能具有的形式,可匹配多个符号串

3.2 词法单元说明

Regular Expression, 正则表达式

意义	代表了字符串的patterns
组成	一系列定义好的字符组合成正则式r
其他概念	与regex匹配的字符串叫做r的语言language,L(R) 可用字符叫做符号symbols 可用字符集合叫做字母表alphabet,Σ
注意	单字符集合的regex匹配自己本身: L(a)={a},表示与正则式a匹配的字符串只有a 空字符使用ε,L(ε)={ε}

regex的运算

运算	优先级	描述
选择运算	最低	"r\|s",表示匹配r或s中的一个,不能同时匹配也不能匹配ε
连接运算	中等	"rs",表示匹配rs的连接,不能只匹配其中一个
闭包/重复	最高	"r",表示对前的r重复0到有限次的匹配 ⭐*L((ab))={ε,ab,abab,...}**

例3.1 正规式书写

3.3 tokens的识别--状态转换图

转换 transition	箭头+匹配条件
开始状态 start	start
接收状态 accepting	两个同心圆,代表识别的结束
回退 backtracking	接收状态+*,表示回退,即不接受最后一个传入字符

3.4 正规式->自动机

参考链接: 编译原理：有穷自动机（DFA与NFA）

确定性有穷自动机(DFA):从每一个状态只能发出一条具有某个符号的边,不能出现同一个符号出现在同一状态发出的两条边上
非确定性有穷自动机(NFA):允许从一个状态发出多条具有相同符号的边,甚至允许发出标有ε符号的边,即NFA可以不输入任何字符就自动沿ε边转换到下一个状态

Rex to NFA

三种运算的转换

rs
r\|s
r*

举例:letter(letter|digit)* (注意优先级)

NFA to DFA

概念

ε-closure	状态集T的ε闭包,可由0或多次ε转换从T中状态到达的所有状态集合
move[T,a]	所有可以从T中某一状态出发,经过一条a(可跳过a边前的任意条ε边)可抵达的所有状态集合
Dtran[T,a]	Dtran[T,a]=ε-closure(move[T,a]) Dtran[T,a]就是状态集T经过一条a可达到的所有状态的集合

子集构造法

构造转换表

确定表头:表列数=字母表字符数+1
填表:一行一列为ε-closure(S0),初始状态的闭包,依次求Dtran[]
循环:直到所有Dtran[]都在第1列上出现过为止

重命名状态

每列子集都作为状态重新编号,把第1行第1列作为初态,以1代表,凡含有接收态的状态都作终态,其余为非初非终态

转换为DFA

最小化DFA

等价/可区别状态

对于一个DFA,如果从状态s出发能够读出某字α,从状态t出发也能读出同样的字α,反之亦然,则称状态s和状态t等价,其余为可区别状态--显然终态和非终态式可区别状态

最小化过程

首先把S分成终态组I和非终态组J，此时,Π={l,J}
拆分状态集,执行move(i, a/b..),move(J, a/b..)当结果状态分布在不同的子集是,则I/J可继续拆分
循环直到不可分

无对应转换

当某个字符a上没有转换的状态,引入状态d表示a上的错误转换,否则容易再最后分组时遗漏,最后在Π中丢弃d即可

⭐例3.2 子集构造法NFA转换成DFA

Ch3 例题

原目录：编译原理 / Ch3 词法分析

查看语雀原文

例3.1 正规式书写

①(a|b)*(ab)(a|b)*

②(bb)*

③(a*ba*ba*)*
④a(a|b)*aa|aa

(a|b)*表示ε,a,b,ab,ba...任何ab组合

⭐例3.2 子集构造法NFA转换成DFA

对(a|b)*a|b,①画出NFA;②NFA转换为DFA;③最小化DFA;

NFA如下

转换表如下:

Dtran[T,a]

Dtran[T,b]

{1,2,3,4,6,9,11}

{5,8,3,4,6,9,10,13}

{7,8,3,4,6,9,12,13}

{5,8,3,4,6,9,10,13}

{7,8,3,4,6,9}

{7,8,3,4,6,9,12,13}

{5,8,3,4,6,9,10,13}

{7,8,3,4,6,9}

{5,8,3,4,6,9,10,13}

{7,8,3,4,6,9}

由于13为接收状态,则转换后2,3,4为最终态

最小化

由②,I={2,3,4},J={1},Π={{1},{2,3,4}},move(I,a)={2},move(I,b)={4},而二者都属于分组{2,3,4},该状态集中状态彼此等价,J无需再拆分,则最终状态集Π={{1},{2,3,4}},令{2}代表{2,3,4}

Ch4 语法分析

原目录：编译原理

查看语雀原文

1. 语法分析位置

通过语法分析器输入tokens,语法分析器(parser)生成一棵分析树

2. 上下文无关文法

CFG(Context-Free Grammars)是编程语言语法结构的规范,使用类似于正则表达式的词汇结构规范

定义

,非终结符的有限非空集合
, 终结符的有限非空集合
, 开始符号
, 产生式

组成

non-terminals	非终态符号,某个语法变量,代表一组或一类结构
terminals	终态符号,即某个词法单元名,如<keyword, if>中的if
start symbol	一个terminal,通常未首先列出的,此符号的串集合即文法生成语言
production	产生式,描述了terminals和non-terminals组成串的方法

产生式的递归

production分为左右递归,区别在于:对于产生式A,左(右)递归时右部中定义A的规则中non-terminal作为第一个(最后一个)symbol出现

$A->Aα|β\ 左递归\\ A->αA|β\ 右递归$

推导

产生式作为一组规则(合法的tokens),能通过其推出串(句子),过程即为"推导"(derivations)

最左/右推导

leftmost:替换每个句型的最左non-terminal
rightmost:替换每个句型的最右non-terminal

分析树

分析树作为推导图形化,忽略了non-terminals应用顺序,因此推导和分析树之前存在一对多关系;但是parsing tree和最左/最右推导存在唯一对应关系

二义性

给定某种语言/句子,求其文法,此时可能产生二义性问题,比如2+5*6,可以理解为(2+5)*6也可以是2+(5*6).给出定义:一个文法可生成多棵分析树时,该文法是二义的

⭐证明

一个句子有多个最左(最右)推导/可画出多棵parsing tree

二义性解决

在构造文法时必须要避免二义性,通常从优先级(preference)和结合性(associativity)入手

优先级:让优先级低的运算符放在离开始符号近的production中(即用更多步骤得到更高优先级的符号)

结合性:

左递归production中的运算符是左结合的(语言从左向右执行)
右递归production中的运算符是右结合的

3. ⭐构造无二义性的CFG

总结:

由①任何语言,先判断优先级,n个优先级需要n+1个非终符号(结果n+1个式子)
由②,先判断语言的因子factor产生式->"语言的最小运算元素num,id|[当语言可以使用括号时(exp)]"
由③④,从高优先级开始构造,最高优先级的production->"使用rule|factor"
由④,依次向下,其余优先级production->"使用rule|高一级production"
直到抵达最低优先级,即开始符号exp的production
最终生成按优先级从低到高最后写factor
以上每一步的production还应考虑结合性进行转化

例4.1 后缀表达式的无二义性CFG构造

⭐例4.2 由num,id和二目运算符+,-,*,/构成表达式的CFG构造

Ch4 例题

原目录：编译原理 / Ch4 语法分析

查看语雀原文

例4.1 后缀表达式的无二义性CFG构造

分析

通常后缀表达式如12+76-*

优先级:1级->需2个非终态符号factor和exp
结合性:左结合

解决

factor:num作为最小元素,且无()参与

factor->num

exp:通常规则都是exp exp opt

exp->exp exp opt | factor,此时opt作为rule的最右侧已经满足左递归

结果

exp->exp exp opt | factor
factor -> num

化简: exp -> exp exp opt | num

⭐例4.2 由num,id和二目运算符+,-,*,/构成表达式的CFG构造

分析

1级左结合 * /

2级左结合 + -

解决

factor:num,id最小元素,可有()参与

factor->num | id | (exp)

1级:二目运算一般规则,取符号term

term->term * term | term / term | factor

考虑左结合 term->term * factor | term / factor | factor

2级:二目运算一般规则,取符号exp

exp->exp + exp | exp - exp | term

考虑左结合 exp -> exp + term | exp -term | term

结果

exp -> exp + term | exp -term | term
term->term * factor | term / factor | factor
factor->num | id | (exp)

⭐例4.3 完整的LL(1)分析过程

有左递归,无左因子

消除左递归

整理文法

L->SL'

L'->,SL'|ε

S->(L), S->a

L->SL',

L'->,SL', L'->ε

如下

消除左递归

整理文法

first(S)={(,a}

first(L)={(,a}

first(L')={, ,ε}

first((L))={(}

first(a)={a}

first(SL')={(,a}

first(,SL')={,}

①由S->(L):
first())-ε∈follow(L) follow(L)={),$}
②由L->SL'
follow(L)∈follow(L') first(L')-ε∈follow(S)
follow(L')={),$} follow(S)={, ,$}

③由L'->,SL'且first(L')含有ε
follow(L')∈follow(S)

first(L')-ε∈follow(S) follow(S)={, , ) ,$}

最后
follow(S)={, , ) ,$} follow(L)={),$} follow(L')={),$}

由a,b结果(提示:填表时始终对应拆分整理后的文法,一行一行扫描)

M[N,T]	(	)	,	a	$
S	S->(L)			S->a
L	L->SL'			L->SL'
L'		L'->ε	L'->,SL'		L'->ε

已知(()()

步骤	stack	input	action
1	S$	(()()$	S->(L)
2	(L)$	(()()$	match
3	L)$	()()$	L->SL'
4	SL')$	()()$	S->(L)
5	(L)L')$	()()$	match
6	L)L')$	)()$	ERROR

例4.4 递归下降程序

构造$A\rightarrow (B)B|ε和B\rightarrow A|ε$的递归下降分析程序

无左递归和左因子,求出first和follow集

文法	first	follow
A->(B)B, A->ε B->A, B->ε	first(A)={(,ε} first(B)={(,ε} first((B)B)={(}	follow(A)= follow(B)={), $}

程序(递归下降程序无需写转换表,需要first/follow集,但是没有对应case $)

A()

B()

match()

void A(){

switch(Token):

case ( :

match(();

B();

match());

B();

case ):

match(ε);

default: error;

}

void B(){

switch(Token):

case ( :

A();

case ):

match(ε);

default: error;

}

void match(expectedToken){

if(Token==expectedToken)

getToken();

else error;

}

⭐例4.5 Bottom-Up算法综合

文法G：S->S(S)|ε
构造LR（0）项目集的DFA
构造SLR(I)分析表
给出句子（()()的SLR(1)分析过程
构造LR(1)项目集的DFA和LR(1)分析表
构造LALR(1)项目集的DFA和LALR(1)分析表
分析使用LR(1)和LALR(1)方法进行语法分析时,两者可能的不同

令S'->S,得到: ①S'->S ②S->S(S) ③S->ε

易错

S->ε也要在DFA中表示为S->·,直接满足规约
状态2中S->S(·S),求其闭包将S的初始项目S->S(S),S->ε继续加入

分析表如下

follow(S')={$},follow(S)={$,(,)}

State	Action			Goto
	(	)	$	S
0	r3	r3	r3	1
1	s2		acc
2	r3	r3	r3	3
3	s2	s4
4	r2	r2	r2

易错

区分问的是LR(0)还是SLR(1)分析,二者DFA相同,分析表不同

LR(0),不管任何符号都规约
SLR(1)时,对A->γ,只有非终符号a∈Follow(A)时,才在表中对应位置填入r(A->γ)

switch j表示转换到状态j,reduce k表示可规约文法k:A->B,序号意义不同
acc填在扩展开始符号S'可规约状态的$单元格中,此状态其他符号无需规约

过程

step	stack	input	action
1	$0	(()()$	r3	由③S->ε规约,得到S并入栈,Goto进入状态1,由于\|ε\|=0,出栈0个状态0个符号
2	$0S1	(()()$	s2	读入一个Token,switch到状态2
3	$0S1(2	()()$	r3
4	$0S1(2S3	()()$	s2
5	$0S1(2S3(2	)()$	r3
6	$0S1(2S3(2S3	)()$	s4
7	$0S1(2S3(2S3)4	()$	r2	由②S->S(S)规约,得到S并入栈,Goto进入状态4,由于\|S(S)\|=0,出栈4个状态4个符号
8	$0S1(2S3	()$	s2
9	$0S1(2S3(2	)$	r3
10	$0S1(2S3(2S3	)$	s4
11	$0S1(2S3(2S3)4	$	r2
12	$0S1(2S3	$	Error	最终结果时Error/Acc不意味着stack一定要空

LR(1)DFA如下

LR(1) .png

易错以状态0为例说明闭包的叠加:

由文法直接得到

①S'->·S, $

②S ->·S(S), $

③S ->·, $

②"·"后为非终S,继续加入产生式,根据向前看符号求法first(($)={(}

④S ->·S(S), (

⑤S ->·, (

合并得到

①S'->·S, $

②S ->·S(S), $/(

③S ->·, $/(

分析表如下

State	Action			Goto
	(	)	$	S
0	r3		r3	1
1	s2		acc
2	r3	r3		3
3	s5	s4
4	r2		r2
5	r3	r3		6
6	s5	s7
7	r2	r2

LALR(1)的DFA如下:

分析表如下

State	Action			Goto
	(	)	$	S
0	r3		r3	1
1	s25		acc
25	r3	r3		36
36	s25	s47
47	r2	r2	r2

假设给定输入(()

(()()$	r3
(()()$	s2
()()$	r3
()()$	s2
)()$	r3
)()$	s4
()$	r2

LR(1)				LALR(1)
step	stack	input	action	step	stack	input	action
1	$0	(()$	r3	1	$0	(()$	r3
2	$0S1	(()$	s2	2	$0S1	(()$	s25
3	$0S1(2	()$	r3	3	$0S1(25	()$	r3
4	$0S1(2S3	()$	s5	4	$0S1(25S36	()$	s25
5	$0S1(2S3(5	)$	r3	5	$0S1(25S36(25	)$	r3
6	$0S1(2S3(5S6	)$	s7	6	$0S1(25S36(25S36	)$	s47
7	$0S1(2S3(5S6)7	$	Error	7	$0S1(25S36(25S36)47	$	r2
				8	$0S1(25S36	$	Error

LALR(1)比起LR(1)多进行了一步无意义的规约才发现错误

例4.6 Top-Down & Bottom-Up对比

自顶向下分析

构造语法树过程从根节点开始到叶子节点
从开始状态出发,根据给定产生式,推导出给定串
这种方法更易于手工构造出高效的语法分析器

自底向上分析

构造语法树过程从叶子节点开始到根节点
从给定的句子出发规约到文法开始符号
这种方法可处理更多种文法与翻译方案,应对可能产生二义性的文法,故分析软件多使用这种方法

Flex实现词法分析器

原目录：编译原理 / Linux下分析器实现

查看语雀原文

参考链接: Lex使用指南

下载

sudo apt-get install flex

要求

实现C-语言词法分析器,每个Token以<名称,属性值>打印,有5种Tokens,最后通过示例程序验证

未命名图片.png

示例程序

/*A program to perform Euclid's
  Algorithm to compute gcd. */
int gcd (int u,int v){
    if (v==0) return u;
    else return gcd(v, u-u/v*v);
    /*u-u/v*v == u mod v */
}
void main(void){
    int x; 
    int y;
    x = input();
    y = input();
    output(gcd(x,y));
}

实现

新建lex.l文件进行编辑

	%{
	#include<stdio.h>
	%}
	delim [ \t\n]
	ws {delim}+
	letter [A-Za-z]
	digit [0-9]
	id {letter}{letter}*
	num {digit}{digit}*
	comments "/*"([^\*]|(\*)*[^\*/])*(\*)*"*/"
%%
{ws}
else    |   
if  |   
int |
return  |   
void    |
while   {printf(&quot;&lt;keyword, %s&gt;\n&quot;, yytext);}    
{id}    {printf(&quot;&lt;ID, %s&gt;\n&quot;, yytext);}
{num}   {printf(&quot;&lt;NUM, %s&gt;\n&quot;, yytext);}
{comments} {printf(&quot;&lt;COMMENTS, %s&gt;\n&quot;, yytext);}
&quot;+&quot; |
&quot;-&quot; |
&quot;*&quot; |
&quot;/&quot; |
&quot;&lt;&quot; |
&quot;&lt;=&quot;    |
&quot;==&quot;    |
&quot;&gt;&quot; |
&quot;&gt;=&quot;    |
&quot;!=&quot;    |
&quot;=&quot; |
&quot;;&quot; |
&quot;,&quot; |
&quot;'&quot; |
&quot;(&quot; |
&quot;)&quot; |
&quot;[&quot; |
&quot;]&quot; |
&quot;{&quot; |
&quot;}&quot; {printf(&quot;&lt;symbol, %s&gt;\n&quot;, yytext);}
%%

int main(){
    if ((yyin = fopen(&quot;./gcd.c&quot;,&quot;r&quot;))==NULL){
        printf(&quot;Can't open file!\n&quot;);
        return 1;   
    }
    yylex();
    return 0;
}

最复杂处为/*...*/注释的匹配,参考: Lex识别C风格字符串和注释

Bug

直接复制代码时会出现各种字符编码,空格错误,最好手动敲入,保证两个%%识别无误(红色)
"["和"]"始终匹配有误,需要在后面加一个空格"[ " "] "

运行

完成.l文件后

①使用flex lex.l,将.l文件编译为.c文件(默认生成lex.yy.c)

②使用gcc [-o xxx.out] lex.yy.c -lfl编译.c文件为可执行文件

③使用./xxx.out直接运行(目录中要有yyin的指定输入文件)

bison实现语法分析器

原目录：编译原理 / Linux下分析器实现

查看语雀原文

基础

参考链接: 【编译原理】用Yacc做语法分析 yacc / lex 在linux 下使用指南

下载

sudo apt-get install bison

要求

给定下列文法,实现语法分析器

$bexpr \rightarrow bexpr\ \textbf{or}\ bterm\ |\ bterm\\ bterm \rightarrow bterm\ \textbf{or}\ bfactor\ |\ bfactor\\ bfactor \rightarrow \textbf{not}\ bfactor|\ (bexpr)|\ \textbf{true}|\ \textbf{false} $

实现

注意当yacc使用自定义lex文件时,需要在lex开始include自定义yacc生成的头文件

lex

%{
//include自定义yacc生成的头文件
#include "bool.tab.h"
#include <stdio.h>
#include <stdlib.h>
%}
%%
true {yylval=1; return TRUE;}
false {yylval=0; return FALSE;}
.|\n {return yytext[0];}
%%

yacc文件

%{
#include <stdio.h>
#include <string.h>
void yyerror(){
printf("over, place run again\n");
}
%}
// declaration section
%{
#ifndef YYSTYPE
#define YYSTYPE int
#endif
%}
%token TRUE
%token FALSE
%%
// translation section
line : bexpr ‘\n’         { if ( $1==1){printf(&quot;true&quot;);}else{printf(&quot;false&quot;);}} | '\n' ; bexpr : bexpr '&amp;' bterm { if(($ 1==1)&&( $3==1)){$  $=1;}else{$  $=0;} } | bterm ; bterm : bterm '|' bfactor {if(($ 1==0)&&( $3==0)){$  $=0;}else{$  $=1;}} | bfactor ; bfactor :'~' bfactor {if($ 2==1){
 $=0;}else{$ =1;}}
| ‘(‘bexpr’)’   {$$=$2;}
|  TRUE      

|  FALSE
;
%%
int main(void){
return yyparse();
}

编译

flex lex.l 生成lex.yy.c文件
bison -v bool.y 生成bool.tab.c文件,改后缀为.h(-v可生成out文件,记录规约表)
gcc lex.yy.c bool.tab.h -o exe -ll 生成exe可执行文件

Ch1 概述#

1.1 语言处理器#

1.2 编译器的结构

词法分析#

语法分析#

语义分析#

中间代码生成#

(机器无关)优化#

代码生成#

(机器相关)优化#

1.3 其余概念

前端/后端#

符号表

遍(Pass)#

Ch3 词法分析#

3.1 词法单元,词素,模式#

3.2 词法单元说明

Regular Expression, 正则表达式#

regex的运算#

3.3 tokens的识别--状态转换图#

3.4 正规式->自动机

Rex to NFA#

NFA to DFA

概念#

子集构造法

最小化DFA

等价/可区别状态

最小化过程

无对应转换#

Ch3 例题#

例3.1 正规式书写#

⭐例3.2 子集构造法NFA转换成DFA#

Ch4 语法分析#

1. 语法分析位置#

2. 上下文无关文法

定义

组成#

产生式的递归#

推导

最左/右推导

分析树

二义性

⭐证明

二义性解决#

3. ⭐构造无二义性的CFG#

Ch4 例题#

例4.1 后缀表达式的无二义性CFG构造#

⭐例4.2 由num,id和二目运算符+,-,*,/构成表达式的CFG构造#

⭐例4.3 完整的LL(1)分析过程

#

例4.4 递归下降程序#

⭐例4.5 Bottom-Up算法综合#

例4.6 Top-Down & Bottom-Up对比#

Flex实现词法分析器#

下载

要求#

实现#

Bug

运行#

bison实现语法分析器#

基础#

下载

要求#

实现

lex#

yacc文件#

编译#

Ch1 概述

1.1 语言处理器

词法分析

语法分析

语义分析

中间代码生成

(机器无关)优化

代码生成

(机器相关)优化

前端/后端

遍(Pass)

Ch3 词法分析

3.1 词法单元,词素,模式

Regular Expression, 正则表达式

regex的运算

3.3 tokens的识别--状态转换图

Rex to NFA

概念

无对应转换

Ch3 例题

例3.1 正规式书写

⭐例3.2 子集构造法NFA转换成DFA

Ch4 语法分析

1. 语法分析位置

组成

产生式的递归

二义性解决

3. ⭐构造无二义性的CFG

Ch4 例题

例4.1 后缀表达式的无二义性CFG构造

⭐例4.2 由num,id和二目运算符+,-,*,/构成表达式的CFG构造

例4.4 递归下降程序

⭐例4.5 Bottom-Up算法综合

例4.6 Top-Down & Bottom-Up对比

Flex实现词法分析器

要求

实现

运行

bison实现语法分析器

基础

要求

lex

yacc文件

编译