我正在制作一种简单的解释编程语言，使用SLY生成一个AST，我将在不使用SLY的情况下对其进行解释。
目前，我已经能够生成所有的令牌并将其提供给解析器，但它无法识别任何规则，只能识别空规则。
Lexer:
from .sly.lex import Lexer
class ALexer(Lexer):
tokens = { ID, NUMBER, STRING, BOOL, PLUS, TIMES, MINUS, DIVIDE, ASSIGN, LPAREN, RPAREN, COMMA, NL }
ignore = ' t'
# Tokens
@_(r'd+[[.]?d*[f]?]?')
def NUMBER(self, t):
endswithF = t.value.endswith('f')
isfloat = endswithF or t.value.find('.') != -1
t.value = float(t.value[:-1] if endswithF else t.value) if isfloat else int(t.value) # Convert to a numeric value
return t
ID = r'[a-zA-Z_][a-zA-Z0-9_]*'
ID['true'] = BOOL
ID['false'] = BOOL
@_(r'".*"')
def STRING(self, t):
t.value = t.value[1:-1]
return t
# Special symbols
PLUS = r'+'
MINUS = r'-'
TIMES = r'*'
DIVIDE = r'/'
ASSIGN = r'='
LPAREN = r'('
RPAREN = r')'
COMMA = r','
@_(r'true', r'false')
def BOOL(self, t):
t.value = t.value == 'true'
return t
@_(r'n')
def NL(self, t):
self.lineno += 1
def error(self, t):
print("Illegal character '%s'" % t.value[0])
self.index += 1
Util类：
from enum import Enum
class SupportedOp(str, Enum):
CONSTANT = "CONSTANT",
VARIABLE = "VARIABLE",
ARGS_LIST = "ARGS_LIST",
FUNC_CALL = "FUNC_CALL",
STATEMENT = "STATEMENT",
STATEMENT_LIST = "STATEMENT_LIST",
PROGRAM = "PROGRAM",
SUM = '+',
SUB = '-',
DIV = '/',
MUL = '*',
ASSIGNMENT = '='
class ParsedOp(dict):
def __init__(self, op: SupportedOp, *values):
dict.__init__(self, op=op, values=values)
分析器：
class AParser(Parser):
debugfile = 'parser.out'
tokens = ALexer.tokens
precedence = (
#('nonassoc', LESSTHAN, GREATERTHAN), # Nonassociative operators
('left', PLUS, MINUS),
('left', TIMES, DIVIDE)
#('right', UMINUS), # Unary minus operator
)
@_('statement_list')
def program(self, p):
print('program', p[0])
return ParsedOp(SupportedOp.PROGRAM, p[0])
@_('statement BACK_IN_LINES statement_list')
def statement_list(self, p):
print('statement_list', p[0], p[1], p[2])
lst: list = p[1].values[0]
lst.append(p[0])
return ParsedOp(SupportedOp.STATEMENT_LIST, lst)
@_('statement')
def statement_list(self, p):
print('statement_list', p[0])
return ParsedOp(SupportedOp.STATEMENT_LIST, [p[0]])
@_('empty')
def statement_list(self, p):
print('empty statement_list')
return ParsedOp(SupportedOp.STATEMENT_LIST, [])
@_('NL BACK_IN_LINES', 'NL')
def BACK_IN_LINES(self, p):
print('BACK_IN_LINES', p[0])
#unused
return 'NL'
@_('assignment', 'expr')
def statement(self, p):
print('statement', p[0])
return ParsedOp(SupportedOp.STATEMENT, p[0])
@_('ID ASSIGN expr')
def assignment(self, p):
print('assignment', p[0], p[1], p[2])
return ParsedOp(SupportedOp.ASSIGNMENT, p[0], p[2])
@_('expr COMMA expr_list')
def expr_list(self, p):
print('expr_list', p[0], p[1], p[2])
lst: list = p[1].values[0]
lst.append(p[0])
return ParsedOp(SupportedOp.ARGS_LIST, lst)
@_('expr')
def expr_list(self, p):
print('expr_list', p[0])
return ParsedOp(SupportedOp.ARGS_LIST, [p[0]])
@_('empty')
def expr_list(self, p):
print('empty expr_list')
return ParsedOp(SupportedOp.ARGS_LIST, [])
@_('constant')
def expr(self, p):
print('expr', p[0])
return p[0]
@_('ID')
def expr(self, p):
print('expr', p[0])
return ParsedOp(SupportedOp.VARIABLE, p[0])
@_('LPAREN expr RPAREN')
def expr(self, p):
print('expr', p[0], p[1], p[2])
return p[1]
@_('ID LPAREN expr_list RPAREN')
def expr(self, p):
print('expr', p[0], p[1], p[2], p[3])
#if exists p.ID in functions
return ParsedOp(SupportedOp.FUNC_CALL, p.ID, p.expr_list)
@_( 'expr PLUS expr',
'expr MINUS expr',
'expr TIMES expr',
'expr DIVIDE expr')
def expr(self, p):
print('expr', p[0], p[1], p[2])
return ParsedOp(SupportedOp(p[1]), p[0], p[2])
@_('NUMBER', 'STRING', 'BOOL')
def constant(self, p):
print('constant', p[0])
return ParsedOp(SupportedOp.CONSTANT, p[0])
@_('')
def empty(self, p):
print('empty')
pass
def error(self, p):
if p:
print("Syntax error at token", p.type)
# Just discard the token and tell the parser it's okay.
self.errok()
else:
print("Syntax error at EOF")
我不知道我的所有规则是否都是好的，但我对每个规则都进行了注释，只留下未注释的"；常数"；规则很简单，但仍然无法识别。
Main：
tokens_out = lexer.ALexer().tokenize(event.get("code"))
tree = AParser().parse(tokens_out)
我的所有令牌都能很好地识别，所以Lexer没问题。解析器无法识别任何规则。知道吗？
据我所见，您的代码在尝试解析第二条语句之前运行良好。正如您的评论中所建议的，我用输入x=2进行了尝试，结果如下(用pprint模块打印得很好)：
{ 'op': <SupportedOp.PROGRAM: 'PROGRAM'>,
'values': ( { 'op': <SupportedOp.STATEMENT_LIST: 'STATEMENT_LIST'>,
'values': ( [ { 'op': <SupportedOp.STATEMENT: 'STATEMENT'>,
'values': ( { 'op': <SupportedOp.ASSIGNMENT: '='>,
'values': ( 'x',
{ 'op': <SupportedOp.CONSTANT: 'CONSTANT'>,
'values': ( 2,)})},)}],)},)}
但是，一旦你试图解析两个语句——比如说x=2和y=2在不同的行上——事情就会开始分崩离析。
有几个问题，我将尝试一次处理一个。
第一个问题是NLlexer规则不返回任何内容，这意味着不会发出任何令牌。这意味着BACK_IN_LINES规则无法匹配，因为它期望看到一个或多个NL令牌。这会生成一系列解析器错误，您应该在控制台上看到这些错误。
人们很容易对解析器的进度感到困惑。由于解析器看不到NL令牌，所以它看到的是x = 2 y ...。在它看到y的时刻，它还没有减少expr；毕竟，下一个令牌可能是+或其他运算符。但是ID不是2之后可能的标记之一，因此会立即抛出语法错误，结果是expr、statement和statement_list没有被还原，因此它们的还原操作永远不会执行，因此您永远不会看到还原操作中的任何调试输出。这并不意味着该规则没有得到承认；更准确的说法是，这条规则得到了认可，但更长时间的比赛仍然是可能的。
如果通过在NL规则的末尾添加return t来修复lexer，则会遇到第二个问题，即statement_list: statement BACK_IN_LINES statement_list的减少操作。即使对于仅由x=2组成的输入，如果该输入以换行符终止，此错误也会导致解析失败。触发该操作是因为BACK_IN_LINES现在已被识别，因此语法要求statement_list has two subcomponents, a语句(x=2) and astatement_listconsisting of the rest of the input. The rest of the input is empty, which is OK because you allow astatement_list`匹配空输入。但是，正如我所说，这会导致减少行动的执行，而减少行动包括：
lst: list = p[1].values[0]
那条线有几个问题。首先，p[1]是BACK_IN_LINES语法符号；您显然打算使用p[2]，也就是statement_list。所以p[1]是字符串NL，它没有values属性。(这一点从Python回溯中应该很明显，假设你可以看到异常回溯。如果你看不到，你应该认真考虑在Python控制台中调试，而不是使用任何东西。)
但是，当我们将其修复为使用p[2]时，我们仍然会得到一个Python TypeError异常。它不再抱怨str没有values属性，而是抱怨builtin_function_or_method不可下标。builtin_function_or_method是dict对象的values方法，因为p[2]是从dict派生而来的SupportedOp。如果您打算使用values方法，则必须调用它，但我不认为这是您想要的(因此values密钥的名称可能不正确)。您的实际意思是与values键相关的值，这意味着行应该读作：
lst: list = p[2]["values"][0]
但这仍然有点问题。让我们来看看由三行组成的输入的解析结果：
first = 1
second = 2
third = 3
这就产生了(同样，用pprint打印得很漂亮)：
{ 'op': <SupportedOp.PROGRAM: 'PROGRAM'>,
'values': ( { 'op': <SupportedOp.STATEMENT_LIST: 'STATEMENT_LIST'>,
'values': ( [ { 'op': <SupportedOp.STATEMENT: 'STATEMENT'>,
'values': ( { 'op': <SupportedOp.ASSIGNMENT: '='>,
'values': ( 'third',
{ 'op': <SupportedOp.CONSTANT: 'CONSTANT'>,
'values': ( 3,)})},)},
{ 'op': <SupportedOp.STATEMENT: 'STATEMENT'>,
'values': ( { 'op': <SupportedOp.ASSIGNMENT: '='>,
'values': ( 'second',
{ 'op': <SupportedOp.CONSTANT: 'CONSTANT'>,
'values': ( 2,)})},)},
{ 'op': <SupportedOp.STATEMENT: 'STATEMENT'>,
'values': ( { 'op': <SupportedOp.ASSIGNMENT: '='>,
'values': ( 'first',
{ 'op': <SupportedOp.CONSTANT: 'CONSTANT'>,
'values': ( 1,)})},)}],)},)}
如果您仔细查看该输出，您会发现这三个语句确实存在，，但顺序错误。
这是您选择对statement_list:使用正确递归规则的结果
statement_list: statement BACK_IN_LINES statement_list
对于自下而上的解析器(例如Sly生成的LALR(1)解析器)，右递归规则实际上永远不会正确，尽管有时需要它们。如果你可以在左递归规则和右递归规则之间进行选择，你最好的选择是左递归规则：
statement_list: statement_list BACK_IN_LINES statement
这有两个优点。首先，它不需要使用解析器堆栈来保存statement_list的所有中间和不完整子部分，直到到达列表的末尾。更重要的是，它按照您可能期望的执行顺序(从左到右)执行递归非终端的减少操作。
右递归规则从右到左执行归约操作，因为第一个递归归约是最后一个嵌套的statement_list。结果是，我们已经看到：statements以相反的顺序附加到statement_list，从最后一个开始。
将规则重写为左递归很容易。但如果我们做一个天真的改变，我们最终会遇到一个不同的问题。允许但不要求输入以换行符结尾是(可能)可取的。这适用于正确的递归生成，因为statement_list被允许为空。但这对左递归规则没有帮助；具有CCD_ 54选项的左递归规则将CCD_。使用左递归规则，允许statement为空更方便。但不是添加一个"；空语句"；，这会扰乱AST，我们可以在statement_list中添加一个规则，它接受一个空序列而不是一个语句。一旦我们这样做，我们就不需要BACK_IN_LINES了，因为语法逻辑保留在statement_list中。
因此，我们可以删除BACK_IN_LINES，并用以下内容替换statement_list的规则：
@_('statement')
def statement_list(self, p):
print('statement_list', p[0])
return ParsedOp(SupportedOp.STATEMENT_LIST, [p[0]])
@_('empty')
def statement_list(self, p):
print('empty statement_list')
return ParsedOp(SupportedOp.STATEMENT_LIST, [])
@_('statement_list NL')
def statement_list(self, p):
print('statement_list', p[0])
return p[0]
@_('statement_list NL statement')
def statement_list(self, p):
print('statement_list', p[0], p[1], p[2])
lst: list = p[0]["values"][0]
lst.append(p[2])
return ParsedOp(SupportedOp.STATEMENT_LIST, lst)
现在，我们终于得到了预期的解析：
{ 'op': <SupportedOp.PROGRAM: 'PROGRAM'>,
'values': ( { 'op': <SupportedOp.STATEMENT_LIST: 'STATEMENT_LIST'>,
'values': ( [ { 'op': <SupportedOp.STATEMENT: 'STATEMENT'>,
'values': ( { 'op': <SupportedOp.ASSIGNMENT: '='>,
'values': ( 'first',
{ 'op': <SupportedOp.CONSTANT: 'CONSTANT'>,
'values': ( 1,)})},)},
{ 'op': <SupportedOp.STATEMENT: 'STATEMENT'>,
'values': ( { 'op': <SupportedOp.ASSIGNMENT: '='>,
'values': ( 'second',
{ 'op': <SupportedOp.CONSTANT: 'CONSTANT'>,
'values': ( 2,)})},)},
{ 'op': <SupportedOp.STATEMENT: 'STATEMENT'>,
'values': ( { 'op': <SupportedOp.ASSIGNMENT: '='>,
'values': ( 'third',
{ 'op': <SupportedOp.CONSTANT: 'CONSTANT'>,
'values': ( 3,)})},)}],)},)}