编译原理简明教程（第3版）-课件 第4--6章 词法分析、语法分析--自顶向下、 语法分析-自底向上.pptx

新工科建设·计算机类系列教材;6;;;;;;;;;;;;标识符或保留字;;设无符号数为：

t=….…E…

(整数部分)(小数部分)(指数部分)

令W=……1

P=…e=

则t=W-1

读无符号数的程序流程图见图4.7;;;;;

1、辅助定义

在使用LEX语言时，先将高级语言的词法写成辅助定义式（类似宏定义）。

例：⑴标识符

letter→A|B…|a|b…|z

digit→0|1|…|9

ident→letter(letter|digit)*

⑵整常数

integer→digit(digit)*;⑶一般实常数

sign→+|-|ε

signinteger→signinteger

decimal→signinteger.integer|sign.integer

⑷含指数部分的实数

exprel→(decimal|signinteger)Esigninteger

⑸实常数

real→decimal|exprel

;2.识别规则（规定了相应词法分析程序的功能）;标识符:

letter

{if(keyword(id)!=0)return(keyword(id));

else{return(15);

return(id)}}

keyword()查保留字表，=0未查到

;3.用户子程序（辅助函数部分）;;;28;29;;新工科建设·计算机类系列教材;6;;语法分析是编译过程的核心部分。

-----在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。;;;例:文法G[S]:S?ABA?abB?cd|cBd

判断abccdd是否是句子。

(1)自顶向下构造语法树

S

AB

abcBd

cd;;例:G[E]:E?E+T|T

T?T*F|F

F?(E)|i

则:First(E+T)={(,i}

First(T)={(,i}

First(T*F)={(,i};2.Follow集(向前看集);3.Select集(可选集);例:对于G[E]

select(E?E+T)=First(E+T)={(,i}

select(E?T)=First(T)={(,i}

select(T?T*F)=First(T*F)={(,i}

select(T?F)=First(F)={(,i}

select(F?(E))=First((E))={(}

select(F?i)=First(i)={i}

;例:G[S]:

S?aBc|bB

B?bB|d|ε

Select(B?ε)=Follow(B)={#,c};;分析时可能出现:

(1)回溯

(2)死循环,在没有对当前输入符号匹配就进入处

理S的过程，无法确定什么时候才用S?b替换,

造成死循环.

解决方法:

文法的实用限制(算法6)

消除左递归

扩充的BNF表示法;2.回溯问题;首先:对每条规则A?β,

First(β)β≠ε

求Select(A?β)=

Follow(A)β=ε

当β≠ε时,对于当前输入符号a,若

a∈First(β)

则可选A?β进行推导,但A有n个候选式,

∴分两种情况.;(1)首符号不同;(2)首符号相同;例:U?αx1|αx2|x3|…|xn

且First(xi)∩First(xj)=Φ,(i,j≥3,i≠j