%%
/*识别规则，每条规则中的动作都用大括号括起来*/
“main”|”int”|”if” {Upper(yytext,yyleng);
printf(\ {id} {printf(\ “+”|”-”|”*” {printf(\\\n\%%
/*辅助过程*/
Upper(char *s,int l) { int i;
for(i=0;i< l;i++) s[i]=toupper(s[i]); return 1;} void main(void) { yylex(); }
LEX的实现
LEX的功能是根据LEX源程序构造一个词法分析程序， 该词法分析器实质上是一个有穷自动机。
LEX的工作原理是将LEX源程序中的正规式转换成DFA，进一步通过控制程序识别单词
第3章 语法分析
主要内容： 1 文法和语言 2 推导与语法树 3 自上而下分析方法 4 自下而上分析方法 5 LR分析法
主要开发了推导与语法树以及几种语法分析的方法。
推导与语法树
给定文法G[S], ??δ为该文法的句型,
若 S==>?Aδ,且A==>?, 则?是句型??δ相对于A的短语； 若 S==> ?Aδ, 且A==> ?, 则?是句型??δ相对于A的简单短语 直观理解：短语就是某句型中的子串，这个子串是由某个非终结 符通过至少一步推导得到的子串，而简单短语就是由某个非终结 符通过一步推导得到的子串。
素短语是一个短语,它至少包含有一个终结符号,并且除它自身以外不再包含其他素短语.其中最左边的素短语称为最左素短语。 例2-1求句型T+T*F+i的短语、简单短语、 句柄、素短语、最左素短语 短语：T+T*F+i, T+T*F, T,T*F,i 简单短语：T,T*F,i 句柄：T
素短语：T*F和i（因为T不包含终结符, T+T*F+i和T+T*F包含其他素短语） 最左素短语：T*F
自上而下分析法
EEET+T+TFi T*F 图2-7 句型T+T*F+i的的语法树 所谓的自上而下分析方法，就是从文法的开始符号出发，根据文法的规则进行推导，最终推导出给定的句子来。包括递归下降分析法和LL(1)分析法。
递归下降分析法是一种自上而下的分析方法，文法的每个非终结符对应一个递归过程。分析过程就是从文法开始符出发执行一组递归过程，这样向下推导直到推出句子；或者说从根结点出发，自上而下为输入串寻找一个最左匹配序列，建立一棵语法树。
LL(1)分析法又称预测分析法，是一种不带回溯的非递归自上而下分析法。 LL(1)分析法基本思想：自左向右扫描分析输入符号串从识别符号开始生成句子的最左推导
LL(1):向前看一个输入符号，便能唯一确定产生式 LL(k):向前看k个输入符号，才能唯一确定产生式 LL(1)分析法主要是构造FIRST集和FOLLOW集。 例2-2 G[E]： E→TE'
E'→+TE'|? T→FT' T'→*FT'|? F→(E)|i
求FIRST集。 解：FIRST(F)={(,i}
FIRST(T’)={*,ε}
FIRST(T)=FIRST(F)-{ε}={(,i} FIRST(E’)={+,ε}
FIRST(E)= FIRST(T)-{ε}={(,i} FIRST(TE’)=FIRST(T)-{ε}={(,i}
FIRST(+TE’)={+} FIRST(ε)={ε} FIRST(FT’)= FIRST(F)-{ε}={(,i} FIRST(*FT’) ={*} FIRST(（E）)={(} FIRST(i)={i} 例2-3 G[E]：
E→TE' E'→+TE'|? T→FT' T'→*FT'|? F→(E)|i
求FOLLOW集。
解：FOLLOW(E)={#,)} ∵E是开始符号∴#∈FOLLOW(E)
又F →(E) ∴ )∈FOLLOW(E) FOLLOW(E’)={#,)} ∵E → TE’ ∴FOLLOW(E)加入 FOLLOW(E’) FOLLOW(T)={+,),#} ∵E’ → +TE’ ∴FIRST(E’)-{ε}加入FOLLOW(T) 又E’?ε， ∴ FOLLOW(E’)加入FOLLOW(T) FOLLOW(T’)= FOLLOW(T)= {+,),#}
FIRST(F)={(,i} FIRST(T’)={*,ε} FIRST(T) ={(,i} FIRST(E’)={+,ε} FIRST(E)={(,i} ∵T → FT’ ∴ FOLLOW(T)加入FOLLOW(T’) FOLLOW(F)={*,+,),#}
∵T → FT’ ∴ FOLLOW(F)=FIRST（T’）-{ε} 又T’?ε ∴ FOLLOW(T)加入FOLLOW(F) 自底向上分析法
自下而上分析法则是从给定的输入串开始，根据文法规则逐步进行归约，直至归约到文法的开始符号为止。
自下而上分析原理是从输入符号串开始，通过重复查找当前句型的“可归约串”并利用有关规则进行规约若能规约为文法的识别符号,则表示分析成功,输入符号串是文法的合法句子,否则有语法错误.
算符优先分析法是一种简单且直观的自上而下分析方法，它适合于程序语言中各类表达式的分析，并且宜于手工实现。所谓算符优先分析，就是依照算术表达式的四则运算过程来进行语法分析，即这种分析方法要预先规定运算符(确切地说是终结符)之间的优先关系和结合性质，然后借助于这种关系来比较相邻运算符的优先级，以确定句型的“可归约串”来进行归约。因此，算符优先分析法不是一种规范归约，在整个归约过程中起决定性作用的是相继两个终结符的优先关系。
LR分析法是一种自下而上进行规范归约的语法分析方法，LR指“自左向右扫描和自下而上进行归约”。LR分析法比递归下降分析法、LL(1)分析法和算符优先分析法对文法的限制要少得多，对大多数用无二义的上下文无关文法描述的语言都可以用LR分析器予以识别，而且速度快，并能准确、及时地指出输入串的任何语法错误及出错位置。LR分析法的一个主要缺点是，若用手工构造分析器则工作量相当大，因此必须求助于自动产生LR分析器的产生器。 LR分析算法描述：
将S0移进状态栈，# 移进符号栈，S为状态栈栈顶状态 a=getsym( ) //读入第一个符号给a while(ACTION[S,a]!=acc ) {
if ACTION[S,a]=Si{
PUSH i,a(分别进栈); a=getsym( ) ;//读入下一个符号给a} else if ACTION[S,a]=rj (第j条产生式为A→β) { 将状态栈和符号栈分别弹出|β| 项;push(A); 将GOTO[S’,A] 移进状态栈（S’为当前栈顶状态）;}
else error( );
第4章 语义分析和中间代码生成分析
主要内容： 1 概述 2 属性文法
3 几种常见的中间语言 4 表达式及赋值语句的翻译 5 控制语句的翻译 6 数组元素的翻译
7 过程或函数调用语句的翻译 8 说明语句的翻译
9 递归下降语法制导翻译方法简介
主要介绍了语法制导翻译方法、几种中间语言以及语句的翻译。 语法制导翻译方法
语法制导翻译的方法就是为每个产生式配上一个翻译子程序(称语义动作或语义子程序)，并在语法分析的同时执行这些子程序。语法制导翻译是将语义规则与语法规则相结合，在语法分析的过程中通过执行语义动作，计算语义属性值，从而完成预定的翻译工作。 语法制导翻译分为两种处理方法： （1）语法制导定义（自底向上）：
对每个产生式编制一个语义子程序，在进行语法分析的过程中，当一个产生式获得匹配时，就调用相应的语义子程序实现语义检查与翻译。这种实现方案隐藏了其中语义规则的计算次序等实现细节，不必规定翻译顺序。 （2）翻译方案（自顶向下）：
在产生式右部的适当位置，插入相应的语义动作，按照分析的进程，执行遇到的语义动作。这是一种动作与分析交错的实现方案。 几种常见的中间语言 1．抽象语法树
抽象语法树也称图表示，是一种较为流行的中间语言表示形式。在抽象语