狡猾的解析器：未召回条件规则

Question

您好，我正在 python 中使用 sly 模块构建我的第一门编程语言。我正在学习一些教程，但我对解析器的行为方式有疑问。这是代码：

from sly import Lexer
from sly import Parser

class BasicLexer(Lexer):
    tokens = { NAME, NUMBER, STRING, IF, THEN, ELSE, FOR, FUN, TO, ARROW, EQEQ }
    ignore = '\t '

    literals = { '=', '+', '-', '/', '*', '(', ')', ',', ';' }

    # Define tokens
    IF = r'IF'
    THEN = r'THEN'
    ELSE = r'ELSE'
    FOR = r'FOR'
    FUN = r'FUN'
    TO = r'TO'
    ARROW = r'->'
    NAME = r'[a-zA-Z_][a-zA-Z0-9_]*'
    STRING = r'\".*?\"'

    EQEQ = r'=='

    @_(r'\d+')
    def NUMBER(self, t):
        t.value = int(t.value)
        return t

    @_(r'#.*')
    def COMMENT(self, t):
        pass

    @_(r'\n+')
    def newline(self,t ):
        self.lineno = t.value.count('\n')

class BasicParser(Parser):
    tokens = BasicLexer.tokens

    precedence = (
        ('left', '+', '-'),
        ('left', '*', '/'),
        ('right', 'UMINUS'),
        )

    def __init__(self):
        self.env = { }
    @_('')
    def statement(self, p):
        pass

    @_('FOR var_assign TO expr THEN statement')
    def statement(self, p):
        return ('for_loop', ('for_loop_setup', p.var_assign, p.expr), p.statement)

    @_('IF condition THEN statement ELSE statement')
    def statement(self, p):
        return ('if_stmt', p.condition, ('branch', p.statement0, p.statement1))

    @_('FUN NAME "(" ")" ARROW statement')
    def statement(self, p):
        return ('fun_def', p.NAME, p.statement)

    @_('NAME "(" ")"')
    def statement(self, p):
        return ('fun_call', p.NAME)

    @_('expr EQEQ expr')
    def condition(self, p):
        return ('condition_eqeq', p.expr0, p.expr1)

    @_('var_assign')
    def statement(self, p):
        return p.var_assign

    @_('NAME "=" expr')
    def var_assign(self, p):
        return ('var_assign', p.NAME, p.expr)

    @_('NAME "=" STRING')
    def var_assign(self, p):
        return ('var_assign', p.NAME, p.STRING)

    @_('expr')
    def statement(self, p):
        return (p.expr)

    @_('expr "+" expr')
    def expr(self, p):
        return ('add', p.expr0, p.expr1)

    @_('expr "-" expr')
    def expr(self, p):
        return ('sub', p.expr0, p.expr1)

    @_('expr "*" expr')
    def expr(self, p):
        return ('mul', p.expr0, p.expr1)

    @_('expr "/" expr')
    def expr(self, p):
        return ('div', p.expr0, p.expr1)

    @_('"-" expr %prec UMINUS')
    def expr(self, p):
        return ('neg', p.expr)

    @_('NAME')
    def expr(self, p):
        return ('var', p.NAME)

    @_('NUMBER')
    def expr(self, p):
        return ('num', p.NUMBER)

if __name__ == '__main__':
    lexer = BasicLexer()
    parser = BasicParser()
    env = {}
    while True:
        try:
            text = input('basic > ')
        except EOFError:
            break
        if text:
            tree = parser.parse(lexer.tokenize(text))
            print(tree)

据我了解，条件规则是非终结符，BNF 表示是： condition : expr EQEQ expr。如果我输入“a == b”，我会得到错误 sly: Syntax error at line 1, token=EQEQ ('var', 'b')。我知道这是想要的行为，因为在语句之外提供此输入没有任何意义，但我想了解为什么不召回条件方法。谢谢！

Answer 1

尽管我们将此技术称为 bottom-up 解析，但实际上它仍然是 top-down，因为语法是从根开始应用的在本例中是 起始符号 ，在 statement.

解析“bottom-up”的原因是解析树的构造。不像 top-down 解析，在解析 child 节点之前立即预测下一个树节点（并添加到解析树），bottom-up 解析器首先解析 child 节点，只有在所有 children 都被减少后，它才会添加 parent 节点。因此，根节点是最后添加到树中的东西；这棵树是自下而上建造的。 [注1]

这为解析器提供了更大的灵活性，因为它不需要确切地知道要预测哪个产生式。它可以预测多种可能性并并行探索它们。（这可以使用状态机在线性时间内完成。）

实际上，condition 只有在它 可能是 下一个要解析的东西时才变得相关。在您的语法中，这仅发生在 IF 标记之后，因此它不适用于您的样本输入。

下面是解析过程的简要总结。（如果您还没有接触过 finite state machines，这可能不太容易理解。）了解以下内容很有用：

项是文法中的单个产生式，带有位置标记（写为•），表示当前输入位置。
一个 itemset 是一组项目。解析器有一个有限状态机，其状态是项集。由于产生式的数量是有限的，因此可能的项目数量也是有限的，因此项目集的数量也是有限的。这使得预先计算有限状态机成为可能。
如果一个项目的末尾有位置标记，则该项目可以减少；位置标记在项目末尾的事实表明整个生产已被识别。减少产量实际上创造了一个 parse-tree 节点（或道德等价物）。
由于此解析器具有（一个符号的）前瞻性，因此每个可简化项也有一个前瞻性集，它只是一组终端。仅当下一个输入符号在此集合中时才能执行缩减。我不打算讨论这个集合是如何计算的。这个集合一般写在[...].
如果位置标记在项目的任何其他位置，则可以进行 shift 或 goto 转换。 shift 当当前状态中的位置标记正好在终端之前并且该终端是下一个输入令牌时执行。当位置标记刚好在 non-terminal 之前并且 non-terminal 刚刚被减少时，执行 goto 转换。 goto 转换取自开始识别 non-terminal 时处于活动状态的状态。（解析器使用堆栈来跟踪状态历史。）
通过从项目集中选择位置标记在终端之前的项目或已识别的 non-terminal 并在这些项目中推进位置标记来处理移位和转到。选中的项是下一个状态的项集（但请看下面的点）。
如果位置标记位于以 non-terminal 开头的项目的开头，则该 non-terminal 的所有产生式都将添加到项目集中，并且它们的位置标记位于开始。（这可能需要重复进行。）
状态机的初始状态是一个表示文法开始符号的项目，后面跟着一个end-of-input标记（通常写成$），位置标记在开头。该项目集按照上述步骤展开。

根据你的语法，状态机的起始状态是项集→•:

START      → • statement $
statement  → •                 [ $ ]
statement  → • FOR var_assign TO expr THEN statement
statement  → • IF condition THEN statement ELSE statement
statement  → • FUN NAME "(" ")" ARROW statement
statement  → • NAME "(" ")"
statement  → • expr
statement  → • var_assign
expr       → • expr "+" expr
expr       → • expr "-" expr
expr       → • expr "*" expr
expr       → • expr "/" expr
expr       → • "-" expr
expr       → • NAME
expr       → • NUMBER
var_assign → • NAME "=" expr
var_assign → • NAME "=" STRING

请注意，此项目集中没有 condition 的产生式，因为它不能位于从开始符号生成的句子的开头。

第一个输入的标记是a，这是一个NAME。这不允许减少 statement → •，因此下一个状态由标记后带有 NAME 的项目组成：

statement  → NAME • "(" ")"
expr       → NAME •            [ "+", "-", "*", "/", ELSE, $ ]
var_assign → NAME • "=" expr
var_assign → NAME • "=" STRING

现在下一个标记是 EQEQ。此时，状态机卡住了。不可能进行移位操作，并且唯一的减少操作在其前瞻集中没有 == 。所以产生语法错误。

备注

令人困惑的是，与 window 之外的树不同，数学树的根在顶部，叶子在底部。另外，这棵树也有可能不是真正建成的；随你（由你决定。但是总是有一个隐式树由动作函数的执行顺序定义：首先是 children，最后是 parent.

狡猾的解析器：未召回条件规则

Sly parser: condition rule not recalled

python

parsing

lexer

sly

备注