学习野牛:什么是无语境语法和LALR(1)？

Question

我正在读这个野牛介绍.

我有两个问题,如果有人能帮助我理解,那就太好了:

1. 这context free grammar意味着什么？

2. 从上面的链接:Bison不是所有的无上下文语言都可以处理,只有那些是LALR(1).简而言之,这意味着必须能够告诉如何使用单个前瞻标记来解析输入字符串的任何部分.它是什么意思"可以告诉如何只用一个前瞻标记来解析输入字符串的任何部分"

Answer 1

无上下文语法是对一组字符串的描述,这些字符串严格地比正则表达式更强大,但仍然可以由机器轻松处理.更正式地说,无上下文语法包含四个方面:

• 一组终端符号,它们是正在生成的字符串的元素.对于野牛解析器,这通常是扫描仪生成的令牌集.对于像英语这样的自然语言的语法,这可能是所有英语单词的集合.

• 一组非终结符号.直觉上,非终结符号表示类似词性的内容,例如"名词"或"动词".

• 一套制作.每个产品都说明了如何用其他一组终端和非终端替换非终结符号.例如,生产Variable -> Type Name说如果我们看到非终结符号Variable,我们可以用字符串替换它Type Name.

• 甲开始符号,它是非末端从其中推导开始.

作为示例,请考虑C样式函数声明的这种简单的无上下文语法:

Function -> Type ident(Arguments)
Type -> int
Type -> Type *
Arguments -> e   (the empty string)
Arguments -> ArgList
ArgList -> Type ident
ArgList -> Type ident, ArgList

这里,起始符号是Function.鉴于此语法,我们可以通过重复选择非终结符号并将其替换为匹配作品的右侧之一来生成C样式的函数声明.在每一步中,我们到目前为止构建的字符串称为句子形式.例如,以下是一些可以从上面的语法派生的不同函数声明:

Sentential Form                       Production
-------------------------------------------------------------------
Function                              Function -> Type ident(Arguments)
Type ident(Arguments)                 Type -> int
int ident(Arguments)                  Arguments -> e
int ident()

Sentential Form                       Production
-------------------------------------------------------------------
Function                              Function -> Type ident(Arguments)
Type ident(Arguments)                 Type -> Type*
Type* ident(Arguments)                Type -> int
int* ident(Arguments)                 Arguments -> ArgList
int* ident(ArgList)                   ArgList -> Type ident, ArgList
int* ident(Type ident, ArgList)       ArgList -> Type ident
int* ident(Type ident, Type ident)    Type -> Type*
int* ident(Type* ident, Type ident)   Type -> Type*
int* ident(Type** ident, Type ident)  Type -> int
int* ident(int** ident, Type ident)   Type -> int
int* ident(int** ident, int ident)

大多数编程语言都有一个可以通过无上下文语法描述的结构.解析器的工作是获取程序和语法,并确定如何通过语法生成该程序.

至于LALR(1),遗憾的是LALR(1)的正式定义并非无足轻重.我刚刚完成了编译器构建课程的教学,在第一次花两个讲座讨论相关的解析技术后,我们才能谈论LALR(1).如果您想要对材料进行正式介绍,可以在课程网站上找到自下而上解析的幻灯片.

LALR(1)是一种称为自下而上解析算法的解析算法,这意味着它尝试以相反的顺序应用语法的产生以将程序减少回起始符号.例如,让我们考虑一下这个字符串,它是由上面的语法生成的:

int** ident(int* ident)

在自下而上的解析中,我们将通过一次查看一个令牌来解析该字符串.每当我们发现可以逆转到某些非终结的东西时,我们就会这样做.(更确切地说,LALR(1)仅在满足其他条件时才进行这些减少,以便算法具有更多上下文,但对于此示例,我们不需要担心这一点).解析中的每个步骤都被称为shift或reduce.一个转变意味着我们看看输入获得什么减少申请更多的信息之一,更多的令牌.一减少,我们采取的令牌和非终结符的一些数字和反向生产要回一些非终结手段.

这是字符串自下而上解析的痕迹:

Workspace           Input                     Action
-----------------------------------------------------------------
             int** ident(int* ident)   Shift
int             ** ident(int* ident)   Reduce Type -> int
Type            ** ident(int* ident)   Shift
Type*            * ident(int* ident)   Reduce Type -> Type*
Type             * ident(int* ident)   Shift
Type*              ident(int* ident)   Reduce Type -> Type*
Type               ident(int* ident)   Shift
Type ident              (int* ident)   Shift
Type ident(              int* ident)   Shift
Type ident(int              * ident)   Reduce Type -> int
Type ident(Type             * ident)   Shift
Type ident(Type*              ident)   Reduce Type -> Type*
Type ident(Type               ident)   Shift
Type ident(Type ident              )   Reduce ArgList -> Type ident
Type ident(ArgList                 )   Reduce Arguments -> ArgList
Type ident(Arguments               )   Shift
Type ident(Arguments)                  Reduce Function -> Type ident(Arguments)
Function                               ACCEPT

了解轮班和减少非常重要,因为在使用野牛时,您将不变地遇到转换/减少冲突并减少/减少冲突.这些错误意味着解析器生成器确定解析器可能进入无法判断是移位还是减少的状态,或者它应该执行的两次降低中的哪一个.有关如何处理此问题的更多详细信息,请参阅野牛手册.

如果您想了解更多关于无上下文语法和解析算法的信息,那么Grune和Jacobs 有一本名为Parsing Techniques:A Practical Guide,Second Edition的优秀书籍,到目前为止,该书对材料有最好的处理方式.我见过的.它涵盖了各种解析算法,包括许多比LALR(1)更强大的技术,这些技术开始得到更广泛的使用(例如,GLR和Earley).我强烈推荐这本书 - 这是我理解解析的主要原因!

希望这可以帮助!