我正在阅读这个野牛介绍。
我有两个问题，如果有人能帮助我理解，那就太好了：
术语是什么
context free grammar意思？从上面的链接：Bison 可以处理并非所有上下文无关语言，只有那些是 LALR(1) 的语言。简而言之，这意味着必须能够仅用一个前瞻标记来说明如何解析输入字符串的任何部分。“可以告诉如何只用一个前瞻标记来解析输入字符串的任何部分”是什么意思
2438 次
2 回答
21
上下文无关文法是对一组字符串的描述，它比正则表达式更强大，但仍然很容易被机器处理。更正式地说，上下文无关文法由四部分组成：
一组终端符号，它们是正在生成的字符串的元素。对于野牛解析器，这通常是扫描仪生成的一组标记。对于像英语这样的自然语言的语法，这可能是所有英语单词的集合。
一组非终结符号。直观地说，非终结符代表词性之类的东西，例如“名词”或“动词”。
一组作品。每个产生式都说明了如何用其他一组终结符和非终结符替换非终结符。例如，产生
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
了解 shift 和 reduction 很重要，因为在使用 bison 时，您总是会遇到shift/reduce 冲突和reduce/reduce 冲突。这些错误意味着解析器生成器确定解析器可能会进入一种状态，它无法判断是移位还是归约，或者它应该执行两种归约中的哪一种。有关如何处理此问题的更多详细信息，请参阅野牛手册。
如果你想了解更多关于上下文无关语法和解析算法的知识，有一本优秀的书，名为Parsing Techniques: A Practical Guide, Second Edition by Grune and Jacobs，到目前为止，对材料的最佳处理我见过的。它涵盖了各种解析算法，包括许多比 LALR(1) 更强大的技术，它们开始得到更广泛的使用（例如 GLR 和 Earley）。我强烈推荐这本书——这是我非常了解解析的主要原因！
希望这可以帮助！
于 2011-08-24T17:12:53.903 回答
1
1）简单来说——这意味着代码的格式和上下文对于各个部分并不重要，你没有看到它是如何格式化来理解含义的。例如，您可以在一行中编写 C 程序，或者将每个单词放在不同的行中，并且程序的含义相同。 维基百科有更正式的定义。
2) LALR (1) 的含义更复杂，但简单来说，我会将其描述为通过一次阅读一个单词来逐步理解含义——只看到下一个单词/符号——一些口语以不成为 LALR(1) - 当您到达句子末尾时，您无法将句子理解为问题或陈述。一些编程语言也可以以这种方式构建，但我不知道有什么，因为出于实际原因，它们都符合 LALR(1) 语法。然而，我确实认为有一些例外情况，C/C++ 需要一个 2 符号向前看才能正确解析语句（因此是 LALR(2)，但由于我不记得它们是什么，我希望有人能指出这一点在评论中。
在任何情况下，本书都是理解编译器和解析器的圣经。
于 2011-08-24T17:10:09.677 回答