2

我试图四处寻找这个问题的答案，但似乎找不到。我正在尝试使用 PLY 编写 Python 中的解析器作为一种组合语言。我的 BNF 的简化版本如下所示：

statement-list -> statement ',' statement-list |
                 'print' expr

statement -> ident 'was' 'a' type |
             ident 'became' expr

type -> 'number' | 'letter'

expr -> factor |
       expr '+' factor |
       expr '-' factor

factor -> number | letter | ident

其中数字和字母就像 int 和 char。

Yacc 文档 ( http://www.dabeaz.com/ply/ply.html#ply_nn23 ) 仅显示简单算术表达式的语法，其中 p[0] 应该是很清楚的。

def p_expression_plus(p):
   'expression : expression PLUS term'
    p[0] = p[1] + p[3]

我的问题是我的 BNF 中的语句列表该怎么办？我有：

def p_statement_list_comma(p):
    'statement-list : statement COMMA statement-list'

但我真的不知道下一步该放什么。任何帮助将不胜感激！

4

2 回答 2

7

我不能代表 PLY 解决方案，但这是一个使用 pyparsing 的解决方案。有时，即使您最终想使用其他库来实现解析器，pyparsing 示例也会很有用，作为快速而简单的原型/练习。不幸的是，这个例子大量使用了这个operatorPrecedence方法，它隐藏了很多中缀解析魔法，所以我不知道你能多容易地翻译它。可以在示例页面 ( http://pyparsing.wikispaces.com/Examples ) 上的 pyparsing wiki 上找到更传统的 expr/term/factor 解析器示例，标题为fourFn.py。

bnf = """
statement-list -> statement ',' statement-list

statement -> ident 'was' 'a' type | 
             ident 'became' expr |
             'print' expr |
             'if' conditional-expr statement

type -> 'number' | 'letter' 

expr -> factor | 
       expr '+' factor | 
       expr '-' factor 

factor -> number | letter | ident 
"""

from pyparsing import (CaselessKeyword, Word, nums, alphas, alphanums, operatorPrecedence, 
    Forward, MatchFirst, opAssoc, oneOf, Group, delimitedList)

PRINT, WAS, A, BECAME, NUMBER, LETTER, IF, ELSE, TRUE, FALSE, AND, OR, NOT = map(
    CaselessKeyword,
    "print was a became number letter if else true false and or not".upper().split())
keyword = MatchFirst([PRINT, WAS, A, BECAME, NUMBER, LETTER, IF, ELSE, TRUE, FALSE, AND, OR, NOT])

typeSpecifier = NUMBER | LETTER

number = Word(nums)
ident = ~keyword + Word(alphas, alphanums+'_')
operand = number | ident

expr = operatorPrecedence(operand,
    [
    ('-', 1, opAssoc.RIGHT),
    (oneOf('* /'), 2, opAssoc.LEFT),
    (oneOf('+ -'), 2, opAssoc.LEFT),
    ])

comparisonExpr = operatorPrecedence(expr,
    [
    ("!", 1, opAssoc.RIGHT),
    (oneOf("< > = <= >= !="), 2, opAssoc.LEFT),
    ])

booleanExpr = operatorPrecedence(TRUE | FALSE | comparisonExpr,
    [
    (NOT, 1, opAssoc.RIGHT),
    (AND, 2, opAssoc.LEFT),
    (OR, 2, opAssoc.LEFT),
    ])

statement = Forward()
printStmt  = PRINT + expr
wasaStmt   = ident + WAS + A + typeSpecifier
becameStmt = ident + BECAME + expr
ifStmt = IF + booleanExpr + statement
statement << Group(printStmt | wasaStmt | becameStmt | ifStmt)

statementList = delimitedList(statement)

tests = """\
    x was a number
    y became 2+5
    print y
    print 100*(5+2)
    print 100*5+2
    if 5 > y print 1000
    if y < 10 y became y+1, print y
    """.splitlines()[:-1]

for t in tests:
    print t.strip()
    for s in statementList.parseString(t).asList():
        print(s)
    print

印刷：

x was a number
['x', 'WAS', 'A', 'NUMBER']

y became 2+5
['y', 'BECAME', ['2', '+', '5']]

print y
['PRINT', 'y']

print 100*(5+2)
['PRINT', ['100', '*', ['5', '+', '2']]]

print 100*5+2
['PRINT', [['100', '*', '5'], '+', '2']]

if 5 > y print 1000
['IF', ['5', '>', 'y'], ['PRINT', '1000']]

if y < 10 y became y+1, print y
['IF', ['y', '<', '10'], ['y', 'BECAME', ['y', '+', '1']]
['PRINT', 'y']

我冒昧地添加print了一种语句，因此它可以出现在程序主体的任何位置。另外，我尝试添加一个 IF-THEN 语句，这确实显示了添加这样一个控制流语句如何开始让你走上编写递归语法的道路（不需要递归只是为了 'was a'、'became '和'打印'）。

于 2011-10-27T05:40:53.253 回答
3

这实际上取决于您如何构建代码以及如何评估它。如果您正在评估，只要它以正确的顺序评估，您不希望在 ie 的文档字符串之后不想要任何东西，p_statement_list_comma就像您拥有它一样 - 无论如何都会评估语句，如果需要您可以保留一个全局变量字典或类似的东西来跟踪某些状态，例如标识符值。

如果您想建立一个解析树，例如如果您不喜欢 ply 的评估顺序，则单独评估，您可以执行以下操作：

def p_statement_list_comma(p):
    'statement-list : statement COMMA statement-list'
    p[0] = [p[1]] + p[3]

def p_statement_print_expr(p):
    'statement-list : PRINT expr'
    p[0] = [p[2]]

这会给你一个语句列表，列表中的最后一个元素是一个表达式。为了简单起见，这里使用列表；如果您愿意，您也可以使用自己的类 - 只需将您想要的任何 python 对象分配给 p[0] ，它将可用于上述级别。

如果您希望从 yacc.parse 返回打印表达式的结果（解析树顶层的值将从 yacc.parse 返回），您可以这样做：

def p_statement_list_comma(p):
    'statement-list : statement COMMA statement-list'
    p[0] = p[3]

def p_statement_print_expr(p):
    'statement-list : PRINT expr'
    p[0] = p[2]
于 2011-10-27T11:52:16.090 回答