编译原理电子课件教案-第7章-自底向上语法分析-LR分析.pptx

1
2
LR(k)分析是指自左向右扫描和自底向上的语法分析。
L:从左至右扫描输入符号串;
R:构造一个最右推导的逆过程;
K:为了作出分析决定而向前看的输入符号的个数。
序
LR分析方法是当前最广义的无回溯的“移进- 归约”方法。
LR(k)分析技术是高德纳(knuth)于1965年首先提出来的。
3
简介:高德纳(1938年),美国著名计算机科学家,斯坦福大学电脑系荣誉教授。高德纳教授被誉为现代计算机科学的鼻祖,在计算机科学及数学领域发表了多部具广泛影响的论文和著作,与 Edsger Wybe Dijkstra并称为我们这个时代最伟大的计算机科学家。
著名成就:
The Art puter Programming
(《计算机程序设计艺术》)的作者
TeX和Metafont排版软件的发明人
LR parsing theory
Knuth–Morris–Pratt算法
Knuth-pletion algorithm
图灵奖史上最年轻获奖者高德纳:
把一件平常事做到人间极致
4
5
自动分析工具GNU bison
(Yet piler),由Bell实验室于1979年开发
exp : term | exp "+" term | exp "-" term ;
注释化的语法规则
能够直接编译运行的语法分析器源代码
8
预备知识:自底向上语法分析概述
LR分析的组成结构
LR分析表(依赖于具体文法)
由两个矩阵组成,其功能是指示分析器的动作
是移进还是规约,根据不同的文法类要采用不
同的构造方法
驱动程序
执行分析表所规定的动作
分析栈
暂存分析器状态以及文法符号
9
所谓自底向上分析方法就是
从输入串开始,逐步进行归约,直到归约到文法的开始符号
或者说
从语法树的末端开始,步步向上归约,直到根结点
自底向上语法分析的实质是一种移进-归约分析法:
对输入串从左向右扫描,并逐个移进栈中。边移入边分析,一旦栈顶符号串形成某个句型的可归约串(它对应某产生式右部),就用该产生式左部的非终极符代替它,完成一步归约。
重复这一过程,直至归约到栈中只剩右界符‘#’和文法的开始符号为止,此时表示分析成功,否则报错。
预备知识:自底向上语法分析概述
10
1. 规范推导、规范句型和规范归约