use*_*783 9 lua parsing recursive-descent context-free-grammar ll-grammar
根据维基百科上的"递归下降解析器",只有LL(k)语法才能实现没有回溯(也就是预测解析)的递归下降.
在其他地方,我已经读过Lua的实现使用这样的解析器.但是,该语言不是 LL(k).事实上,Lua天生就是含糊不清的:是a = f(g)(h)[i] = 1指a = f(g); (h)[i] = 1还是a = f; (g)(h)[i] = 1？这种歧义通过解析器中的贪婪来解决(因此上面被解析为错误的a = f(g)(h)[i]; = 1).
这个例子似乎表明预测解析器可以处理不是LL(k)的语法.事实上,它们是否能够处理LL(k)的超集？如果是这样,有没有办法找出一个给定的语法是否在这个超集中？
换句话说,如果我正在设计一种我想使用预测解析器解析的语言,我是否需要将语言限制为LL(k)？或者我可以适用更宽松的限制吗？
为了对递归下降解析器进行适当的定义，通过递归下降只能解析LL（k）语言是绝对正确的。
可以使用递归下降解析器来解析Lua正是因为该语言是LL（k）。也就是说，Lua存在LL（k）语法。[注1]
如果存在识别该语言的LL（k）语法，则该语言为LL（k）。这并不意味着识别该语言的每个语法都是LL（k）；可能有许多种可以识别该语言的非LL（k）语法。因此，某种语法不是LL（k）的事实绝对不能说明语言本身。
在形式语言理论中，仅当语言的每个语法都模棱两可时，该语言才具有固有的歧义。可以肯定地说，没有一种实用的编程语言本质上是模棱两可的，因为实际的编程语言是经过确定性地解析的（以某种方式）。[笔记2]。
因为编写严格无歧义的语法可能很乏味，所以语言文档提供歧义语法以及指示如何解决歧义的文本材料非常普遍。
例如，许多语言（包括Lua）都带有语法文档，该语法未明确包含运算符优先级，从而允许使用简单的表达式规则：
exp ::= exp Binop exp | Unop exp | term
该规则显然是模棱两可的，但是如果给出了运算符列表，它们的相对优先级以及每个运算符是左关联还是右关联的指示，则可以将该规则机械地扩展为明确的表达语法。实际上，许多解析器生成器允许用户分别提供优先级声明，并在生成解析器的过程中执行机械扩展。应该注意，生成的解析器是用于歧义语法的解析器，因此原始语法的歧义并不意味着解析算法能够处理歧义语法。
可以机械地消除歧义的参考语法的另一个常见示例是在类似C的语言中发现的“悬而未决”的歧义（但在Lua中没有）。语法：
if-statement ::= "if" '(' exp ')' stmt
| "if" '(' exp ')' stmt "else" stmt
当然是模棱两可的；目的是使解析为“贪婪的”。同样，模棱两可不是固有的。有一种机械转换可以产生明确的语法，如下所示：
matched-statement ::= matched-if-stmt | other-statement
statement ::= matched-if-stmt | unmatched-if-stmt
matched-if-stmt ::= "if" '(' exp ')' matched-statement "else" matched-statement
unmatched-if-stmt ::= "if" '(' exp ')' statement
| "if" '(' exp ')' matched-statement "else" unmatched-if-stmt
解析器生成器隐式执行此转换是很常见的。（对于LR解析器生成器，实际上是通过将reduce动作与shift动作冲突来删除来实现该转换的。这比转换语法要简单，但效果完全相同。）
因此，Lua（和其他编程语言）并不是天生就有歧义的。因此，可以使用需要明确确定性解析器的解析算法来解析它们。确实，对于某些语言来说，每种可能的语法都是模棱两可的，这甚至可能有点令人惊讶。正如上面引用的Wikipedia文章所指出的那样，此类语言的存在已由Rohit Parikh于1961年证明；固有的上下文无关语言的一个简单示例是
{anbmcmdn|n,m≥0} ∪ {anbncmdm|n,m≥0}。
与上面悬空的else结构一样，Lua语句序列的消歧仅通过允许贪婪的解析来执行。直观地讲，该过程很简单；它基于禁止两个连续的语句（中间没有分号），其中第二个语句以可能会继续第一个的令牌开头。
在实践中，实际上并不需要执行此转换。它可以在解析器的构造过程中隐式完成。因此，在这里我不会费心生成一个完整的Lua语法。但是我相信，这里Lua语法的一小部分足以说明转换是如何进行的。
以下子集（主要基于参考语法）精确显示了OP中指示的歧义：
program ::= statement-list
statement-list ::= Ø
| statement-list statement
statement ::= assignment | function-call | block | ';'
block ::= "do" statement-list "end"
assignment ::= var '=' exp
exp ::= prefixexp [Note 3]
prefixexp ::= var | '(' exp ')' | function-call
var ::= Name | prefixexp '[' exp ']'
function-call ::= prefixexp '(' exp ')'
（注：（我使用的是Ø代表空字符串，而不是?， ?或%empty）。
Lua语法为左递归，因此显然不是LL（k）（与歧义无关）。可以机械地去除左递归；为了证明子集是LL（1），我在这里做了足够的工作。不幸的是，转换后的语法不能保留语法分析树的结构，这是LL（k）语法的经典问题。在递归下降解析过程中重建正确的解析树通常很简单，我不再赘述。
提供的LL（1）版本很简单exp，但是结果消除了var（可以分配给）和function-call（不能分配）之间的区别：
exp ::= term exp-postfix
exp-postfix ::= Ø
| '[' exp ']' exp-postfix
| '(' exp ')' exp-postfix
term ::= Name | '(' exp ')'
但是现在我们需要重新创建区别，以便能够解析赋值语句和函数调用。这很简单（但是不会促进对语法IMHO的理解）：
a-or-fc-statement ::= term a-postfix
a-postfix ::= '=' exp
| ac-postfix
c-postfix ::= Ø
| ac-postfix
ac-postfix ::= '(' exp ')' c-postfix
| '[' exp ']' a-postfix
为了使贪婪的解析明确的，我们需要禁止（从语法）的任何事件，其中有两端，并开始以“（”。实际上，我们需要区分不同类型的报表，根据是否不该语句以a开头，并且独立于该语句是否以。结尾（实际上，只有三种类型，因为没有以a开头但不以。结尾的语句[注4]）S1 S2S1expS2(exp(exp
statement-list ::= Ø
| s1 statement-list
| s2 s2-postfix
| s3 s2-postfix
s2-postfix ::= Ø
| s1 statement-list
| s2 s2-postfix
s1 ::= block | ';'
s2 ::= Name a-postfix
s3 ::= '(' exp ')' a-postfix
在最常见的用法中，预测递归下降解析器是LL（k）算法的一种实现，其中每个非终端都映射到一个过程。每个非终端过程都使用一个可能的先行长度表k来决定要使用的非终端产品的替代生产方式，然后简单地逐个符号“执行”生产符号：终端符号使下一个输入符号成为如果匹配，则丢弃；如果不匹配，则报告错误；非终结符导致非终结过程被调用。
可以使用FIRST k和FOLLOW k集构造先行序列表。（如果A→ω是α，则将生产映射到一系列终端。）[注5]α ∈ FIRSTk(ω FOLLOWk(A))
使用递归下降解析的此定义，递归下降解析器可以精确且仅处理LL（k）语言。[注6]
然而，LL（k）和递归下降语法分析器的取向忽略一个递归下降语法分析器，它是它是，首先是一个重要的方面，一种程序正常地写入在一些图灵完整的编程语言。如果允许该程序稍微偏离上述严格的结构，则它可以解析更大的一组语言，甚至不是上下文无关的语言。（例如，参见注释2中引用的C上下文敏感性。）
特别是，向表中提前映射到生产的表中添加“默认”规则非常容易。这是一个非常诱人的优化，因为它大大减小了超前表的大小。通常，默认规则用于非终结符，其替代方案包括一个空的右侧，在LL（1）语法的情况下，它将映射到该非终结符的FOLLOW集中的任何符号。在该实现中，先行表仅包括FIRST中的先行设置，解析器自动为任何其他符号产生一个空的右侧，对应于立即返回。（与LR（k）解析器中的类似优化一样，此优化可以延迟错误的识别，但是在读取其他令牌之前仍可以识别错误。）
LL（1）解析器不能包含可空的非终端，该终端的FIRST和FOLLOW集包含一个公共元素。但是，如果递归下降解析器使用“默认规则”优化，则在构造解析器期间将永远不会注意到该冲突。实际上，忽略冲突允许从（某些）非确定性语法构造“贪婪”解析器。
这非常方便，因为正如我们上面所看到的，产生明确的贪婪语法是一项繁重的工作，并且即使是隐约地类似于语言的清晰表达，也不会导致任何事情。但是改进的递归解析算法并不强大。它只是解析等效的SLL（k）语法（实际上没有构造该语法）。
我无意提供上述断言的完整证明，但第一步是要观察到任何非终端都可以重写为新的非终端的析取，每个非终端都有一个单独的FIRST令牌，可能还有一个新的非终端，右侧为空。然后“仅”需要通过创建新的析取来从FOLLOW可为空的非终结符集中删除非终结符。
在这里，我说的是在标记化流上运行的语法，其中删除了注释，并将其他构造（例如用“长括号”分隔的字符串）简化为单个标记。如果没有这种转换，该语言将不会是LL（k）（因为注释-可以任意长-会干扰前瞻标记的可见性）。这使我也可以回避用LL（k）语法可以识别多长时间括号的问题，这与该问题并不特别相关。
有些编程语言无法通过上下文无关的语法来确定性地进行解析。最臭名昭著的例子可能是Perl，但是还有一个众所周知的C构造(x)*y，它只能使用有关该符号的信息x（无论是变量名还是类型别名）以及正确解析C ++的困难来确定性地进行解析。涉及模板的表达式。（见，例如，这些问题为什么不能C ++解析与LR（1）语法分析器？并且是C ++上下文无关的或上下文敏感？）
为简单起见，我删除了各种文字常量（字符串，数字，布尔值等）以及表构造函数和函数定义。这些标记不能成为函数调用的目标，这意味着以这些标记之一结尾的表达式不能用带括号的表达式扩展。删除它们可以简化歧义的说明；完整的语法仍然可以实现该过程，但这更加乏味。
对于完整的语法，我们还需要考虑不能用a扩展的表达式(，因此将有四个不同的选项。
确定性LL（k）语法无法使用此算法生成明确的解析表，Sippu和Soisalon-Soininen将该算法称为Strong LL（k）算法。可以使用类似于LR（k）解析器中状态的附加解析状态来增强算法。这对于特定的语法可能很方便，但是不会更改LL（k）语言的定义。正如Sippu和Soisalon-Soininen所证明的那样，可以从任何LL（k）语法机械推导产生完全相同语言的SLL（k）语法。（请参阅第2卷中的定理8.47）。
递归定义算法是基于规范堆栈的LL（k）解析器的精确实现，其中解析器堆栈是在解析器执行期间使用当前连续性和激活记录堆栈的组合隐式构造的。
| 归档时间： |
|
| 查看次数： |
1792 次 |
| 最近记录： |