讨厌英文的同学，请
不小心乱玩后悔了的话，请，说不定会恢复
首先解释一下基本概念
词法分析和语法分析：编译或者解释一门语言，必经两个步骤：词法分析和语法分析，词法分析就是把源代码的字符流变成计算机可理解的词汇：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的第一个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 ●
显而易见，我们可以总结出下面两条规律：
所有以●结尾的状态，操作就是规约,其它状态操作就是移入。
假如当前状态● 后是一个非终结符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)分析过程
阅读(...) 评论()2013编译原理复习题及***_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
2013编译原理复习题及***
上传于||文档简介
&&编译原理复习题
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩22页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢第四章 语法分析(1)_图文_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
第四章 语法分析(1)
上传于||暂无简介
大小：595.00KB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢第四章 语法分析和语法分析程序 课后***【khdaw_lxywyl】_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
第四章 语法分析和语法分析程序 课后***【khdaw_lxywyl】
上传于||文档简介
&&编译原理答案
阅读已结束，如果下载本文需要使用5下载券
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩33页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢语法分析_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
上传于||文档简介
&&Javac编译器语法分析介绍
阅读已结束，如果下载本文需要使用0下载券
想免费下载更多文档？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩30页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢
