• 打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮
  • 打赏支付宝扫一扫

首页

 > 

设计架构 > 

数据结构

语法分析算法LR(1)基础教程(上)

winter-cnwinter-cn • 7年前
目录
基本概念
定义语法BNF/EBNF
LL与LR
LR(1)状态机构建
下篇:LR(1)分析过程
讨厌英文的同学,请点我碰碰运气
不小心乱玩后悔了的话,请再碰碰运气,说不定会恢复
基本概念

首先解释一下基本概念

词法分析和语法分析:编译或者解释一门语言,必经两个步骤:词法分析和语法分析,词法分析就是把源代码的字符流变成计算机可理解的词汇:token,语法分析就是把token流变成一颗结构化的语法树,以便后面的程序去翻译或者分析。比如,假如计算机要想识别整数四则运算,词法分析器那么就要认识整数、加减乘除四种运算符号,以及左右括号这些token,而要根据运算符的结合性,把四则运算构建成语法树。

3 + 4 × 5

最后得到的语法树可能长成下面的样子

AdditiveExpression:

    AdditiveExpression

        MultipleExpression:

            Integer:3

        "+"

    MultipleExpression:

        Integer:4

        "×"

        Integer:5

上面这颗树用编程语言中的数据结构表达出来,就是比较容易被计算机理解和处理的了。(设计模式中的Interpreter模式,就是省略前面的步骤直接使用这种结构的)

词法分析可以简单地用正则表达式来完成,而本文则专门讲一种语法分析的经典算法:LR(1)

定义语法——BNF/EBNF

上面我们提到了四则运算,不过我们没有严格定义四则运算到底是什么,比如,有没有括号、用×还是*来表示乘法,但是计算机语言需要一个非常严谨的定义方式,现在广泛使用的就是BNF及其扩展EBNF。如我们以以下方式定义带括号四则运算:

<Expression> ::= <AdditiveExpression>

<AdditiveExpression> ::=  <AdditiveExpression> "+" <MultipleExpression> | <AdditiveExpression> "-" <MultipleExpression> | <MultipleExpression>

<MultipleExpression> ::= <MultipleExpression> "×" <PrimaryExpression> | <MultipleExpression> "/" <PrimaryExpression> | <PrimaryExpression>

<PrimaryExpression> ::= "(" <Expression> ")" | <Integer>

其中Expression、AdditiveExpression、MultipleExpression 、PrimaryExpression、Integer我们成为Symbol(语法符号,C++链接器报的错误里面说找不到符号,就是这个词),词法分析产生的每一个token也同时是Symbol,如果一个Symbol可以由若干个Symbol组成,那么称为non-terminal symbol(非终结符),否则称terminal symbol,最后生成语法树以后,terminal symbol就是所有的叶子节点。

因为对BNF的一些批评,后来出现了EBNF,它是BNF的扩展版本。

Expression ::= AdditiveExpression

AdditiveExpression ::=  AdditiveExpression "+" MultipleExpression , AdditiveExpression "-" MultipleExpression , MultipleExpression

MultipleExpression ::= MultipleExpression "×" PrimaryExpression , MultipleExpression "÷" PrimaryExpression , PrimaryExpression

PrimaryExpression ::= "(" Expression ")" , Integer

在现在大多数语言规范中,都在使用BNF/EBNF或者与之非常接近的方法来描述语法。

 

LL与LR

常见的语法分析算法有LL和LR。

LL的第一个L表示from Left to right,第二个L表示Left most推导。

LR的第一个L和LL的第一个L含义相同,第二个R表示Right most推导。

在通常的描述中,后面还有一个括号里面的数字如,LL(0)、LL(1)、LL(4)、LR(0)、LR(1)这样,括号里面的数字表示用于决策所需的后续token数。

 

 

 

LR(1)状态机构建

LR(1)分析从外部看起来,每次接受一个字符,最后接收程序终结符时,内部刚好形成一颗语法树。

在内部,每当我们接受一个Symbol之后,我们就需要做一个决定:是把新的Symbol跟原有的Symbol立即合并成更高级的Symbol,还是把新的Symbol暂放呢?

在LR(1)中,有两个术语:reduce(归约)和shift(移入)。规约就是把已经读入的低级Symbol组合成高级Symbol,如Integer "x" Integer 可以reduce成MultipleExpression

仍然以上面的 3 + 4 × 5 为例,当我们接受3的时候,实际上3已经是一个完整的PrimaryExpression了,而进一步,一个PrimaryExpression也是MultipleExpression,我们可以一直将3归约到一个完整的Expression

Expression:

    AdditiveExpression:

        MultipleExpression:

            PrimaryExpression:

                Integer:3

但是我们此时不应当直接reduce到Expression,这是一个错误的语法树结构。

 

考虑以下两种情况:

3 + 4 × 5,在读入×时,

此时 3 + 4显然不应该被reduce

3 × 4 + 5,在读入+时

此时 3 × 4 显然应该被reduce

 

为了正确处理以上的问题,我们要构建一个状态机来指导LR(1)运算,何时reduce,何时shift。

由BNF我们可以得到的语法规则,以四则运算为例,最终我们想要的是一个Expression,即我们的语法树最终根节点是Expression 。

我们认为输入的token序列最终会形成一个Expression,那么考虑一个问题,状态机的最初状态0,能够接受哪些Symbol的shift呢?

第一个考虑到,状态机可以接受Expression这个Symbol,这将导致我们进入最终状态。

此外因为有语法规则Expression ::= AdditiveExpression,状态0还能接受AdditiveExpression

又因为有语法规则AdditiveExpression ::=  MultipleExpression "+" MultipleExpression , MultipleExpression "-" MultipleExpression , MultipleExpression

状态0还能接受MultipleExpression

……

 

从这个分析过程不难看出,状态0可以接受所有Expression,以及所有能生成Expression的规则的第一个Symbol,并按此规则递归。

 

接下来我们要关心迁移问题了,毫无疑问接受Expression这个Symbol以后,直接进入最终状态,然而对于其它情况,如接受了一个MultipleExpression ,则会产生更多可能性,我们把AdditiveExpression ::=  MultipleExpression "+" MultipleExpression , MultipleExpression "-" MultipleExpression , MultipleExpression看成3条规则,把所有的规则全都拆分出来.

每一条规则都将会形成若干状态迁移规则:


Expression ::= AdditiveExpression

● AdditiveExpression

AdditiveExpression ●


AdditiveExpression ::=  AdditiveExpression "+" MultipleExpression , AdditiveExpression "-" MultipleExpression , MultipleExpression

● AdditiveExpression "+" MultipleExpression

AdditiveExpression ● "+" MultipleExpression

AdditiveExpression "+" ● MultipleExpression

AdditiveExpression "+" MultipleExpression ●

● AdditiveExpression "-" MultipleExpression

AdditiveExpression ● "-" MultipleExpression

AdditiveExpression "-" ● MultipleExpression

AdditiveExpression "-" MultipleExpression ●

● MultipleExpression

MultipleExpression ●


MultipleExpression ::= MultipleExpression "×" PrimaryExpression , MultipleExpression "÷" PrimaryExpression , PrimaryExpression

● MultipleExpression "×" PrimaryExpression

MultipleExpression ● "×" PrimaryExpression

MultipleExpression "×" ● PrimaryExpression

MultipleExpression "×" PrimaryExpression ●

● MultipleExpression "÷" PrimaryExpression

MultipleExpression ● "÷" PrimaryExpression

MultipleExpression "÷" ● PrimaryExpression

MultipleExpression "÷" PrimaryExpression ●

● PrimaryExpression

PrimaryExpression ●


PrimaryExpression ::= "(" Expression ")" , Integer

● "(" Expression ")"

"(" ● Expression ")"

"(" Expression ● ")"

"(" Expression ")" ●

● Integer

Integer ●


显而易见,我们可以总结出下面两条规律:

  1. 所有以●结尾的状态,操作就是规约,其它状态操作就是移入。
  2. 假如当前状态● 后是一个非终结符X,那么所有能规约到X的规则中以●开头的状态迁移规则也适用于当前状态。

我们现在可以认为● Expression是初始状态,Expression ● 是结束状态,根据规则2,可以得到以下状态迁移适用当前状态

● AdditiveExpression

● AdditiveExpression "+" MultipleExpression

● AdditiveExpression "-" MultipleExpression

● MultipleExpression

● MultipleExpression "×" PrimaryExpression

● MultipleExpression "÷" PrimaryExpression

● PrimaryExpression

● "(" Expression ")"

● Integer

同样开头的迁移规则必须归并,实际上,第一次我们可以得到JSON表示的以下状态结构(我们用JS程序员最喜欢的$表示reduce)

{

    AdditiveExpression:{

        "+": {MultipleExpression:{$:"AdditiveExpression"}},

        "-": {MultipleExpression:{$:"AdditiveExpression"}},

        $: "Expression"

    },

    MultipleExpression:{

        "×": {PrimaryExpression:{$:"MultipleExpression"}},

        "÷": {PrimaryExpression:{$:"MultipleExpression"}},

        $: "AdditiveExpression"

    },

    PrimaryExpression:{$:"MultipleExpression"},

    "(":{Expression:{")":{$:"PrimaryExpression"}}},

    Integer:{$:"PrimaryExpression"}

}

注意,这个状态迁移关系仅仅是分析了第一个状态后的结果,要想得到完整地状态机,还要对所有后续状态递归地应用规则2。这将可能产生无限循环,为了避免这种情况,我们应该对每个状态做hash,然后把循环的情况直接指向之前的结果。

做完这些之后,我们就得到了一个完整的LR(1)状态机。

 

下篇:LR(1)分析过程
“看完这篇还不够?如果你也在学习IT,并希望记录自己的成长日志,请戳这里告诉我们!”
新人作者

好好学习,天天向上,有工作有兼职可以找我。微信号:gethost

文章总数
总阅读量
程序猿们,如果你或你的朋友想升职加薪,请狠戳这里我要成长
参与讨论
后参与讨论
winter-cn
新人作者

文章总数
总阅读量
程序猿们,如果你或你的朋友想升职加薪,请狠戳这里我要成长
48h快讯7天最热月榜More
  • 7年前

    Dijkstra算法(单源最短路径)单源最短路径问题,即在图中求出给定顶点到其它任一顶点的最短路径。在弄清楚如何求算单源最短路径问题之前,必须弄清楚最短路径的最优子结构性质。一.最短路径的最优子结构性质该性质描述为:如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,k和s是这条路径上的一个中间顶点,那么P(k,s)必定是从k到s的最短路径。下面证明该性质的正确性。假设P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路
    收起
  • 7年前

    二叉树的非递归遍历二叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树,有前序、中序以及后序三种遍历方法。因为树的定义本身就是递归定义,因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法,就要采用栈去模拟实现。在三种遍历中,前序和中序遍历的非递归算法都很容易实现,非递归后序遍历实现起来相对来说要难一点。一.前序遍历前序遍历按照根结点-左孩子-右孩子的顺序进行访问。1.递归实现voi
    收起
  • 7年前

    淘宝名词解释产品和商品的区别:淘宝标准化产品,由类目+关键属性唯一确定。如:手机类目,关键属性是品牌和型号,NokiaN95就是一个产品,nokia是品牌,N95是型号。产品除了关键属性还包括一般信息、销售属性和非关键属性。参考:如"诺基亚N95"就是一个产品。通过类目的关键属性组合来确定唯一的产品。后台标准类目叶子节点下,一组共同特征商品的组合(例如:化妆品+雅芳+保湿单品+容量),属于同一个产品的商品可以认为对消费者的效用及使用感受是没有差别的。产品这个概念对淘宝这种C2
    收起
  • 5年前

    队列特性:先进先出(FIFO)先进队列的元素先出队列。来源于我们生活中的队列(先排队的先办完事)。队列有下面几个操作:InitQueue()  初始化队列EnQueue()进队列DeQueue()出队列IsQueueEmpty()判断队列是否为空IsQueueFull()判断队列是否已满队列可以由数组和链表两种形式实现队列操作(c语言),下面仅以数组为例:数组实现:队列数据结构typedefstructqueue
    收起
  • 7年前

    前言那个啥前面发了2篇文章讲这个商品表的设计,后面越多需求浮出水面才发现设计依旧有问题,好吧,乐观一点,正如我博客的标题一样,我在进化^_^为什么要这样设计先说几个需求,看看您现在是如何去实现:一个用户来到我们网站,在前台页面,1.他要买洗发水,他进入了洗发水的类别,他想买带去屑止痒功效的500ml的洗发水,能否直接搜索出来所有品牌带这个功效属性是500ml的洗发水2.接着他要买一件T恤,他想买V领,短袖的T恤,能否直接通过2个属性搜索出所有品牌的T恤展示给他3.他
    收起
  • 9年前

    1、反转一个链表。循环算法。1Listreverse(Listl){2if(!l)returnl;3listcur=l.next;4listpre=l;5listtmp;6pre.next=null;7while(cur){8tmp=cur;9cur=cur.ne
    收起
  • 7年前

    图的遍历图的遍历有两种遍历方式:深度优先遍历(depth-firstsearch)和广度优先遍历(breadth-firstsearch)。1.深度优先遍历基本思想:首先从图中某个顶点v0出发,访问此顶点,然后依次从v0相邻的顶点出发深度优先遍历,直至图中所有与v0路径相通的顶点都被访问了;若此时尚有顶点未被访问,则从中选一个顶点作为起始点,重复上述过程,直到所有的顶点都被访问。可以看出深度优先遍历是一个递归的过程。如下图中的一个无向图其深度优先遍历得到的序
    收起
  • 7年前

    1:原理以此比较相邻的两个元素,每次比较完毕最大的一个字跑到本轮的末尾。目的:按从小到大排序。方法:假设存在数组:72,54,59,30,31,78,2,77,82,72第一轮比较相邻两个元素,如果左边元素大于右边元素,则交换。72和54比较的结果就是,54在前,72在后;然后72和59比较的结果,59在前,72在后;以此类推,第一轮比较之后的结果是:54,59,30,31,72,2,77,78,72,82经过第一轮比较,最大的元素跑到了最
    收起
  • 9年前

    CodehighlightingproducedbyActiproCodeHighlighter(freeware)http://www.CodeHighlighter.com/-->/*冒泡排序基本思想将n个记录看作按纵向排列,每趟排序时自下至上对每对相邻记录进行比较,若次序不符合要求(逆序)就交换。每趟排序结束时都能使排序范围内关键字最小的记录象一个气泡一样升到表上端的对应位置,整个排序过程共进行n-1趟,依次将关键字最小、次小、第三小的各个记录冒到表的第一个、第二个、第三个位置
    收起