编译原理张晶版第五章自底向上优先分析法详解.ppt

第五章 优先分析法; 语法分析 推导： —自上而下的语法分析过程 —预测分析程序，递归下降分析法（最左推导） —注：要求文法是LL(1)文法 归约： —自下而上的语法分析过程 —简单优先分析法，算符优先分析法、LR分析法;一、自下而上的语法分析过程;a+b………#;注：1）初态时栈内仅有栈底符“#”，读头指在最左边的单词符号上 . 2）语法分析程序执行的动作： a)移进：读入一个单词并压入栈内，读头后移； b)归约：检查栈顶若干个符号能否进行归约，若能，就以产生式左部替代该符号串，同时输出产生式编号. c)识别成功：移进—归约的结局是栈内只剩下栈底符号和文法开始符号，读头也指向语句的结束符. d)识别失败. ;例如：有文法如下： (1) S aAcBe (2) A b (3) A Ab (4) B d 问语句abbcde是不是该文法的合法语句?;步骤;二、确定的自下而上语法分析;5.1 简单优先分析法;5.1 简单优先分析法一、基本思想;5.1 简单优先分析法二、简单优先文法;对任何X,若文法开始符号S X……,则# X;若有S …..X,则X # ; PDA读入一个单词后，比较栈顶符号和该单词 的优先级，若栈顶符号优先级低于该单词，继续读入；若栈顶符号优先级高于或等于读入符号，则找句柄进行归约，找不到句柄就继续读入，直到最后栈内只剩下开始符号，输入串读到“#”为止，此时识别正确。 四、简单优先分析法的优缺点 优点：算法理解简单，技术简单 缺点：适用范围小，分析尺寸太大;5.2 算符优先分析法一、什么是算符优先分析法;5.2 算符优先分析法;如：i+i-i*(i+i) 归约过程如下： 1）i+i-i*(i+i) 设算数级别最高，最先归约 2）E+i-i*(i+i) 3) E+E-i*(i+i) +,-同级，先归约左边“+” 4）E-i*(i+i) E-E*(i+i) -, ×不同级，先归约右边“×” E-E*(E+i) E-E*(E+E) 先算括号内，再算括号外 E-E*(E) E-E*E 先归约“×”，再归约“+” E-E E;1、确定运算符的优先级 算符优先分析法的关键是比较两个相继出现的终结符的优先级而决定应采取的动作 要完成运算符间优先级的比较，可以先定义各种可能相继出现的运算符的优先级，并表示为矩阵的形式，使得能够在分析中通过查询矩阵元素而得到算符之间的优先关系;2.对于任何两个可能相继出现的终结符a,b，若具有以下形式：“……..ab…….”, “….aQb….”, 其中Q是某非终结符，则a,b之间的关系为： 1） a b,a的优先级低于b 2) a b,a的优先级等于b 3) a b,a的优先级高于b 4) 若ab在任何情况下都不可能相继出现，则ab无关系;5.2 算符优先分析法;注：１）在此表中，＋包括－，＊包括／，“＃”是一个特殊符号，用于语句的开始符号和结束符号. 　　２）这张表满足是通常数学上的习惯约定，值得注意的是： －1).运算量i的优先级高于算符 －2). 语句开始和结束符号“＃”与终结符a相继出现时，应该有＃　　a或a #,以此来保证语句内先归约 （　　　）表示括号是成对归约的 优先关系和代数中的大于小于关系不同,a b并不意味着b a终结符所处的左右位置很重要.;3、直观算符分析法;3、直观算符分析法 1）直观算符分析法使用两个工作栈：一个算符栈（OPTR）存放运算符和括号，一个算量栈（OPND)用于存放操作数和运算结果；OPTR的栈顶符号用Q表示，OPND的栈顶符号用p表示 2）初态时，OPND为空，OPTR只有”#“ 直观算符分析算法如下：;OPND=“”; OPTR=“#” flag=true; advance;/*读入一个单词*/ While flag{ If Q=“#”and SYM=“#”then flag=false/*成功*/ else if Q=“(“and SYM=“)” then /*匹配括号对*/ {OPTR栈顶出栈；advance} else if SYM是算量 then /*移进算量*/ ;{SYM入OPND栈；advance；} else if Q SYM then /*移进算符*/ {SYM入OPTR栈；advance；} else if Q SYM