精选课件第3章.语法分析.ppt

设有OPG文法句型为: #N1a1N2a2…NnanNn+1# 其中Ni为非终结符(可以为空), ai为终结符 定理:一个OPG句型的最左素短语是描述下列条件的最左子串: 　　　aj-1Njaj…NiaiNi+1 aj-1aj aj=aj+1, aj+1= aj+2 ,…, ai-2= ai-1，ai-1= ai ai ai+1 算符优先分析法如何确定当前句型的最左素短语？ 注意:出现在aj左端和a i右端的非终结符号一定属于 这个素短语,因为我们的运算是中缀形式给出 的(OPG文法的特点)NaNaNaN ?NaWaN 例: 文法G[E] E::=E+T|T T::=T*F|F F::=(E)|i 分析文法的句型T+T*F+i 步骤 句型 关系 最左子串 规约符号 1 2 3 4 #T+T*F+i# #T+T+i# #E+i# #E+F# #+*+i# #++i# #+i# #+# T*F T+T i E+F T E E F 例: 文法G[E] E::=E+T|T T::=T*F|F F::=(E)|i 算符优先分析算法描述 k=1,s[k]=‘#’ ;//s为符号栈，‘#’压入栈，s[k]为栈顶项 do{ a=getsym( );//读入下一个符号给a if(s[k] ∈VT ) j=k; else j=k-1; while(s[j] a){ do{//在栈中寻找满足的s[j] s[j+1]=…= s[k] a 的s[j+1] ， 即最左素短语的头 Q= s[j] ; if(s[j-1] ∈VT ) j=j-1; else j=j-2; }while(s[j] =Q) s[j+1]… s[k] ?N; //归约最左素短语 k=j+1; s[k]=N;}//end of while if(s[j] a|| s[j] = a){k=k+1;s[k]=a;} //移进 else error }while(a!=‘#’ || 符号栈中不是#S) 向栈中移进符号，以形成最左素短语 寻找满足的s[j] s[j+1]＝…= s[k] a 的s[j+1] ，即最左素短语的头 算符优先分析算法举例 【例4.23】 设文法G[E]： E→E+T E→T T→T*F T→F F→(E) F→i 试用算符优先分析法分析句子i+i*i。 1.每次规约当前句型的最左素短语 2.不一定是规范规约 构造方法非常简单 分析速度也比较快 诊查错误的能力较弱 适用的范围小 算符优先分析法的优缺点 优点 缺点 优先关系也可以用优先函数表示 f—栈内优先函数 g— 栈外优先函数 若 ab 则令 f(a)g(b) a=b f(a)=g(b) ab f(a)g(b) 什么是LR(k)分析: 　L：从左到右扫描 　R：最右推导的逆过程（最左归约） k：是指为了作出分析决定而向前看的输入符号的个数 是一种规范归约过程 LR(k)分析技术Knuth于1965年首先提出 4.5　LR分析法 适用范围广，适用于多数无二义性的上下文无关文法 分析效率高，报错及时 可以自动生成 手工实现工作量大 LR分析法的优缺点 优点 缺点 总控程序 输出 输入# S1 Xm … S1 … X1 S0 # 栈 状态 文法符号 ACTION GOTO LR分析表 产生式表 LR分析器的逻辑结构：分析栈、分析表、总控程序 4.5.1 LR分析器的逻辑结构和工作过程 (3)分析表的种类：四类 SLR(1)分析表(简单LR分析表) LR(0)分析表 构造简单,最易实现,大多数上下文无关文法都 可以构造出SLR分析表,所以具有较高的实用 价值。使用SLR分析表进行语法分析的分析器 叫SLR分析器 对文法的限制较大，无实用价值，是构造其它LR分析表的基础 （重点掌握） LR(1)分析表(规范LR分析表) 适用文法类最大,几乎所有上下文无关文法都能 构造出L