Помогите мне найти подходящий генератор парсера ruby ​​/ python

Question

Первым генератором парсера, с которым я работал, был Parse :: RecDescent, и доступные для него руководства / учебные пособия были великолепны, но наиболее полезной его функцией были инструменты отладки, в частности трассировка возможности (активируются установкой $ RD_TRACE в 1). Я ищу генератор синтаксического анализатора, который поможет вам отладить его правила.

Дело в том, что он должен быть написан на python или ruby ​​и иметь подробный режим / режим трассировки или очень полезные методы отладки.

Кто-нибудь знает такой генератор парсера?

РЕДАКТИРОВАТЬ: когда я говорил об отладке, я не имел в виду отладку python или ruby. Я имел в виду отладку генератора синтаксического анализатора, посмотрите, что он делает на каждом шаге, посмотрите каждый символ, который он читает, правила, которым он пытается соответствовать. Надеюсь, вы поняли.

BOUNTY EDIT: чтобы выиграть награду, пожалуйста, покажите структуру генератора синтаксического анализатора и проиллюстрируйте некоторые из его функций отладки. Я повторяю, я не заинтересован в pdb, но в структуре отладки парсера. Также, пожалуйста, не упоминайте верхушку дерева. Мне это не интересно.

Answer 1

Python - довольно простой язык для отладки. Вы можете просто сделать импорт pdb pdb.settrace ().

Однако эти генераторы синтаксического анализатора предположительно имеют хорошие средства отладки.

http://www.antlr.org/

http://www.dabeaz.com/ply/

http://pyparsing.wikispaces.com/

В ответ на щедрость

Вот отладка PLY в действии.

Исходный код

tokens = (
    'NAME','NUMBER',
    )

literals = ['=','+','-','*','/', '(',')']

# Tokens

t_NAME    = r'[a-zA-Z_][a-zA-Z0-9_]*'

def t_NUMBER(t):
    r'\d+'
    t.value = int(t.value)
    return t

t_ignore = " \t"

def t_newline(t):
    r'\n+'
    t.lexer.lineno += t.value.count("\n")

def t_error(t):
    print("Illegal character '%s'" % t.value[0])
    t.lexer.skip(1)

# Build the lexer
import ply.lex as lex
lex.lex(debug=1)

# Parsing rules

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

# dictionary of names
names = { }

def p_statement_assign(p):
    'statement : NAME "=" expression'
    names[p[1]] = p[3]

def p_statement_expr(p):
    'statement : expression'
    print(p[1])

def p_expression_binop(p):
    '''expression : expression '+' expression
                  | expression '-' expression
                  | expression '*' expression
                  | expression '/' expression'''
    if p[2] == '+'  : p[0] = p[1] + p[3]
    elif p[2] == '-': p[0] = p[1] - p[3]
    elif p[2] == '*': p[0] = p[1] * p[3]
    elif p[2] == '/': p[0] = p[1] / p[3]

def p_expression_uminus(p):
    "expression : '-' expression %prec UMINUS"
    p[0] = -p[2]

def p_expression_group(p):
    "expression : '(' expression ')'"
    p[0] = p[2]

def p_expression_number(p):
    "expression : NUMBER"
    p[0] = p[1]

def p_expression_name(p):
    "expression : NAME"
    try:
        p[0] = names[p[1]]
    except LookupError:
        print("Undefined name '%s'" % p[1])
        p[0] = 0

def p_error(p):
    if p:
        print("Syntax error at '%s'" % p.value)
    else:
        print("Syntax error at EOF")

import ply.yacc as yacc
yacc.yacc()

import logging
logging.basicConfig(
    level=logging.INFO,
    filename="parselog.txt"
)

while 1:
    try:
        s = raw_input('calc > ')
    except EOFError:
        break
    if not s: continue
    yacc.parse(s, debug=1)

выход

lex: tokens   = ('NAME', 'NUMBER')
lex: literals = ['=', '+', '-', '*', '/', '(', ')']
lex: states   = {'INITIAL': 'inclusive'}
lex: Adding rule t_NUMBER -> '\d+' (state 'INITIAL')
lex: Adding rule t_newline -> '\n+' (state 'INITIAL')
lex: Adding rule t_NAME -> '[a-zA-Z_][a-zA-Z0-9_]*' (state 'INITIAL')
lex: ==== MASTER REGEXS FOLLOW ====
lex: state 'INITIAL' : regex[0] = '(?P<t_NUMBER>\d+)|(?P<t_newline>\n+)|(?P<t_NAME>[a-zA-Z
_][a-zA-Z0-9_]*)'
calc > 2+3
PLY: PARSE DEBUG START

State  : 0
Stack  : . LexToken(NUMBER,2,1,0)
Action : Shift and goto state 3

State  : 3
Stack  : NUMBER . LexToken(+,'+',1,1)
Action : Reduce rule [expression -> NUMBER] with [2] and goto state 9
Result : <int @ 0x1a1896c> (2)

State  : 6
Stack  : expression . LexToken(+,'+',1,1)
Action : Shift and goto state 12

State  : 12
Stack  : expression + . LexToken(NUMBER,3,1,2)
Action : Shift and goto state 3

State  : 3
Stack  : expression + NUMBER . $end
Action : Reduce rule [expression -> NUMBER] with [3] and goto state 9
Result : <int @ 0x1a18960> (3)

State  : 18
Stack  : expression + expression . $end
Action : Reduce rule [expression -> expression + expression] with [2,'+',3] and goto state
 3
Result : <int @ 0x1a18948> (5)

State  : 6
Stack  : expression . $end
Action : Reduce rule [statement -> expression] with [5] and goto state 2
5
Result : <NoneType @ 0x1e1ccef4> (None)

State  : 4
Stack  : statement . $end
Done   : Returning <NoneType @ 0x1e1ccef4> (None)
PLY: PARSE DEBUG END
calc >

Таблица разбора, сгенерированная на parser.out

Created by PLY version 3.2 (http://www.dabeaz.com/ply)

Grammar

Rule 0     S' -> statement
Rule 1     statement -> NAME = expression
Rule 2     statement -> expression
Rule 3     expression -> expression + expression
Rule 4     expression -> expression - expression
Rule 5     expression -> expression * expression
Rule 6     expression -> expression / expression
Rule 7     expression -> - expression
Rule 8     expression -> ( expression )
Rule 9     expression -> NUMBER
Rule 10    expression -> NAME

Terminals, with rules where they appear

(                    : 8
)                    : 8
*                    : 5
+                    : 3
-                    : 4 7
/                    : 6
=                    : 1
NAME                 : 1 10
NUMBER               : 9
error                : 

Nonterminals, with rules where they appear

expression           : 1 2 3 3 4 4 5 5 6 6 7 8
statement            : 0

Parsing method: LALR

state 0

    (0) S' -> . statement
    (1) statement -> . NAME = expression
    (2) statement -> . expression
    (3) expression -> . expression + expression
    (4) expression -> . expression - expression
    (5) expression -> . expression * expression
    (6) expression -> . expression / expression
    (7) expression -> . - expression
    (8) expression -> . ( expression )
    (9) expression -> . NUMBER
    (10) expression -> . NAME

    NAME            shift and go to state 1
    -               shift and go to state 2
    (               shift and go to state 5
    NUMBER          shift and go to state 3

    expression                     shift and go to state 6
    statement                      shift and go to state 4

state 1

    (1) statement -> NAME . = expression
    (10) expression -> NAME .

    =               shift and go to state 7
    +               reduce using rule 10 (expression -> NAME .)
    -               reduce using rule 10 (expression -> NAME .)
    *               reduce using rule 10 (expression -> NAME .)
    /               reduce using rule 10 (expression -> NAME .)
    $end            reduce using rule 10 (expression -> NAME .)


state 2

    (7) expression -> - . expression
    (3) expression -> . expression + expression
    (4) expression -> . expression - expression
    (5) expression -> . expression * expression
    (6) expression -> . expression / expression
    (7) expression -> . - expression
    (8) expression -> . ( expression )
    (9) expression -> . NUMBER
    (10) expression -> . NAME

    -               shift and go to state 2
    (               shift and go to state 5
    NUMBER          shift and go to state 3
    NAME            shift and go to state 8

    expression                     shift and go to state 9

state 3

    (9) expression -> NUMBER .

    +               reduce using rule 9 (expression -> NUMBER .)
    -               reduce using rule 9 (expression -> NUMBER .)
    *               reduce using rule 9 (expression -> NUMBER .)
    /               reduce using rule 9 (expression -> NUMBER .)
    $end            reduce using rule 9 (expression -> NUMBER .)
    )               reduce using rule 9 (expression -> NUMBER .)


state 4

    (0) S' -> statement .



state 5

    (8) expression -> ( . expression )
    (3) expression -> . expression + expression
    (4) expression -> . expression - expression
    (5) expression -> . expression * expression
    (6) expression -> . expression / expression
    (7) expression -> . - expression
    (8) expression -> . ( expression )
    (9) expression -> . NUMBER
    (10) expression -> . NAME

    -               shift and go to state 2
    (               shift and go to state 5
    NUMBER          shift and go to state 3
    NAME            shift and go to state 8

    expression                     shift and go to state 10

state 6

    (2) statement -> expression .
    (3) expression -> expression . + expression
    (4) expression -> expression . - expression
    (5) expression -> expression . * expression
    (6) expression -> expression . / expression

    $end            reduce using rule 2 (statement -> expression .)
    +               shift and go to state 12
    -               shift and go to state 11
    *               shift and go to state 13
    /               shift and go to state 14


state 7

    (1) statement -> NAME = . expression
    (3) expression -> . expression + expression
    (4) expression -> . expression - expression
    (5) expression -> . expression * expression
    (6) expression -> . expression / expression
    (7) expression -> . - expression
    (8) expression -> . ( expression )
    (9) expression -> . NUMBER
    (10) expression -> . NAME

    -               shift and go to state 2
    (               shift and go to state 5
    NUMBER          shift and go to state 3
    NAME            shift and go to state 8

    expression                     shift and go to state 15

state 8

    (10) expression -> NAME .

    +               reduce using rule 10 (expression -> NAME .)
    -               reduce using rule 10 (expression -> NAME .)
    *               reduce using rule 10 (expression -> NAME .)
    /               reduce using rule 10 (expression -> NAME .)
    $end            reduce using rule 10 (expression -> NAME .)
    )               reduce using rule 10 (expression -> NAME .)


state 9

    (7) expression -> - expression .
    (3) expression -> expression . + expression
    (4) expression -> expression . - expression
    (5) expression -> expression . * expression
    (6) expression -> expression . / expression

    +               reduce using rule 7 (expression -> - expression .)
    -               reduce using rule 7 (expression -> - expression .)
    *               reduce using rule 7 (expression -> - expression .)
    /               reduce using rule 7 (expression -> - expression .)
    $end            reduce using rule 7 (expression -> - expression .)
    )               reduce using rule 7 (expression -> - expression .)

  ! +               [ shift and go to state 12 ]
  ! -               [ shift and go to state 11 ]
  ! *               [ shift and go to state 13 ]
  ! /               [ shift and go to state 14 ]


state 10

    (8) expression -> ( expression . )
    (3) expression -> expression . + expression
    (4) expression -> expression . - expression
    (5) expression -> expression . * expression
    (6) expression -> expression . / expression

    )               shift and go to state 16
    +               shift and go to state 12
    -               shift and go to state 11
    *               shift and go to state 13
    /               shift and go to state 14


state 11

    (4) expression -> expression - . expression
    (3) expression -> . expression + expression
    (4) expression -> . expression - expression
    (5) expression -> . expression * expression
    (6) expression -> . expression / expression
    (7) expression -> . - expression
    (8) expression -> . ( expression )
    (9) expression -> . NUMBER
    (10) expression -> . NAME

    -               shift and go to state 2
    (               shift and go to state 5
    NUMBER          shift and go to state 3
    NAME            shift and go to state 8

    expression                     shift and go to state 17

state 12

    (3) expression -> expression + . expression
    (3) expression -> . expression + expression
    (4) expression -> . expression - expression
    (5) expression -> . expression * expression
    (6) expression -> . expression / expression
    (7) expression -> . - expression
    (8) expression -> . ( expression )
    (9) expression -> . NUMBER
    (10) expression -> . NAME

    -               shift and go to state 2
    (               shift and go to state 5
    NUMBER          shift and go to state 3
    NAME            shift and go to state 8

    expression                     shift and go to state 18

state 13

    (5) expression -> expression * . expression
    (3) expression -> . expression + expression
    (4) expression -> . expression - expression
    (5) expression -> . expression * expression
    (6) expression -> . expression / expression
    (7) expression -> . - expression
    (8) expression -> . ( expression )
    (9) expression -> . NUMBER
    (10) expression -> . NAME

    -               shift and go to state 2
    (               shift and go to state 5
    NUMBER          shift and go to state 3
    NAME            shift and go to state 8

    expression                     shift and go to state 19

state 14

    (6) expression -> expression / . expression
    (3) expression -> . expression + expression
    (4) expression -> . expression - expression
    (5) expression -> . expression * expression
    (6) expression -> . expression / expression
    (7) expression -> . - expression
    (8) expression -> . ( expression )
    (9) expression -> . NUMBER
    (10) expression -> . NAME

    -               shift and go to state 2
    (               shift and go to state 5
    NUMBER          shift and go to state 3
    NAME            shift and go to state 8

    expression                     shift and go to state 20

state 15

    (1) statement -> NAME = expression .
    (3) expression -> expression . + expression
    (4) expression -> expression . - expression
    (5) expression -> expression . * expression
    (6) expression -> expression . / expression

    $end            reduce using rule 1 (statement -> NAME = expression .)
    +               shift and go to state 12
    -               shift and go to state 11
    *               shift and go to state 13
    /               shift and go to state 14


state 16

    (8) expression -> ( expression ) .

    +               reduce using rule 8 (expression -> ( expression ) .)
    -               reduce using rule 8 (expression -> ( expression ) .)
    *               reduce using rule 8 (expression -> ( expression ) .)
    /               reduce using rule 8 (expression -> ( expression ) .)
    $end            reduce using rule 8 (expression -> ( expression ) .)
    )               reduce using rule 8 (expression -> ( expression ) .)


state 17

    (4) expression -> expression - expression .
    (3) expression -> expression . + expression
    (4) expression -> expression . - expression
    (5) expression -> expression . * expression
    (6) expression -> expression . / expression

    +               reduce using rule 4 (expression -> expression - expression .)
    -               reduce using rule 4 (expression -> expression - expression .)
    $end            reduce using rule 4 (expression -> expression - expression .)
    )               reduce using rule 4 (expression -> expression - expression .)
    *               shift and go to state 13
    /               shift and go to state 14

  ! *               [ reduce using rule 4 (expression -> expression - expression .) ]
  ! /               [ reduce using rule 4 (expression -> expression - expression .) ]
  ! +               [ shift and go to state 12 ]
  ! -               [ shift and go to state 11 ]


state 18

    (3) expression -> expression + expression .
    (3) expression -> expression . + expression
    (4) expression -> expression . - expression
    (5) expression -> expression . * expression
    (6) expression -> expression . / expression

    +               reduce using rule 3 (expression -> expression + expression .)
    -               reduce using rule 3 (expression -> expression + expression .)
    $end            reduce using rule 3 (expression -> expression + expression .)
    )               reduce using rule 3 (expression -> expression + expression .)
    *               shift and go to state 13
    /               shift and go to state 14

  ! *               [ reduce using rule 3 (expression -> expression + expression .) ]
  ! /               [ reduce using rule 3 (expression -> expression + expression .) ]
  ! +               [ shift and go to state 12 ]
  ! -               [ shift and go to state 11 ]


state 19

    (5) expression -> expression * expression .
    (3) expression -> expression . + expression
    (4) expression -> expression . - expression
    (5) expression -> expression . * expression
    (6) expression -> expression . / expression

    +               reduce using rule 5 (expression -> expression * expression .)
    -               reduce using rule 5 (expression -> expression * expression .)
    *               reduce using rule 5 (expression -> expression * expression .)
    /               reduce using rule 5 (expression -> expression * expression .)
    $end            reduce using rule 5 (expression -> expression * expression .)
    )               reduce using rule 5 (expression -> expression * expression .)

  ! +               [ shift and go to state 12 ]
  ! -               [ shift and go to state 11 ]
  ! *               [ shift and go to state 13 ]
  ! /               [ shift and go to state 14 ]


state 20

    (6) expression -> expression / expression .
    (3) expression -> expression . + expression
    (4) expression -> expression . - expression
    (5) expression -> expression . * expression
    (6) expression -> expression . / expression

    +               reduce using rule 6 (expression -> expression / expression .)
    -               reduce using rule 6 (expression -> expression / expression .)
    *               reduce using rule 6 (expression -> expression / expression .)
    /               reduce using rule 6 (expression -> expression / expression .)
    $end            reduce using rule 6 (expression -> expression / expression .)
    )               reduce using rule 6 (expression -> expression / expression .)

  ! +               [ shift and go to state 12 ]
  ! -               [ shift and go to state 11 ]
  ! *               [ shift and go to state 13 ]
  ! /               [ shift and go to state 14 ]

Answer 2

Я знаю, что награда уже была востребована, но вот эквивалентный парсер, написанный на pyparsing (плюс поддержка вызовов функций с нулем или большим количеством аргументов, разделенных запятыми):

from pyparsing import *

LPAR, RPAR = map(Suppress,"()")
EQ = Literal("=")
name = Word(alphas, alphanums+"_").setName("name")
number = Word(nums).setName("number")

expr = Forward()
operand = Optional('-') + (Group(name + LPAR + 
                                  Group(Optional(delimitedList(expr))) +
                                  RPAR) |
                           name | 
                           number | 
                           Group(LPAR + expr + RPAR))
binop = oneOf("+ - * / **")
expr << (Group(operand + OneOrMore(binop + operand)) | operand)

assignment = name + EQ + expr
statement = assignment | expr

Этот тестовый код запускает синтаксический анализатор по основным шагам:

tests = """\
    sin(pi/2)
    y = mx+b
    E = mc ** 2
    F = m*a
    x = x0 + v*t +a*t*t/2
    1 - sqrt(sin(t)**2 + cos(t)**2)""".splitlines()

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

Дает этот вывод:

sin(pi/2)
[['sin', [['pi', '/', '2']]]]

y = mx+b
['y', '=', ['mx', '+', 'b']]

E = mc ** 2
['E', '=', ['mc', '**', '2']]

F = m*a
['F', '=', ['m', '*', 'a']]

x = x0 + v*t +a*t*t/2
['x', '=', ['x0', '+', 'v', '*', 't', '+', 'a', '*', 't', '*', 't', '/', '2']]

1 - sqrt(sin(t)**2 + cos(t)**2)
[['1', '-', ['sqrt', [[['sin', ['t']], '**', '2', '+', ['cos', ['t']], '**', '2']]]]]

Для отладки добавим следующий код:

# enable debugging for name and number expressions
name.setDebug()
number.setDebug()

А теперь мы повторим первый тест (с отображением входной строки и простой линейки столбцов):

t = tests[0]
print ("1234567890"*10)[:len(t)]
print t
statement.parseString(t)
print

Предоставление этого вывода:

1234567890123
    sin(pi/2)
Match name at loc 4(1,5)
Matched name -> ['sin']
Match name at loc 4(1,5)
Matched name -> ['sin']
Match name at loc 8(1,9)
Matched name -> ['pi']
Match name at loc 8(1,9)
Matched name -> ['pi']
Match name at loc 11(1,12)
Exception raised:Expected name (at char 11), (line:1, col:12)
Match name at loc 11(1,12)
Exception raised:Expected name (at char 11), (line:1, col:12)
Match number at loc 11(1,12)
Matched number -> ['2']
Match name at loc 4(1,5)
Matched name -> ['sin']
Match name at loc 8(1,9)
Matched name -> ['pi']
Match name at loc 8(1,9)
Matched name -> ['pi']
Match name at loc 11(1,12)
Exception raised:Expected name (at char 11), (line:1, col:12)
Match name at loc 11(1,12)
Exception raised:Expected name (at char 11), (line:1, col:12)
Match number at loc 11(1,12)
Matched number -> ['2']

Pyparsing также поддерживает синтаксический анализ пакетов, своего рода напоминание о времени разбора (подробнее о пакетировании здесь ). Вот та же последовательность разбора, но с включенным packrat:

same parse, but with packrat parsing enabled
1234567890123
    sin(pi/2)
Match name at loc 4(1,5)
Matched name -> ['sin']
Match name at loc 8(1,9)
Matched name -> ['pi']
Match name at loc 8(1,9)
Matched name -> ['pi']
Match name at loc 11(1,12)
Exception raised:Expected name (at char 11), (line:1, col:12)
Match name at loc 11(1,12)
Exception raised:Expected name (at char 11), (line:1, col:12)
Match number at loc 11(1,12)
Matched number -> ['2']

Это было интересное упражнение, и мне было полезно увидеть возможности отладки из других библиотек синтаксического анализатора.

Answer 3

Я ничего не знаю о его функциях отладки, но я слышал хорошие отзывы о PyParsing.

http://pyparsing.wikispaces.com/

Answer 4

ANTLR выше имеет преимущество в том, что генерирует читаемый и понятный человеку код, так как это (очень сложный и мощный) нисходящий синтаксический анализатор, так что вы можете пройти через него с помощью обычного отладчика и посмотрите, что он делает на самом деле .

Вот почему это мой генератор парсера.

Недостаток генераторов синтаксического анализатора, таких как PLY, имеет недостаток что для больших грамматик почти невозможно понять что на самом деле означает отладочный вывод и почему таблица разбора такая, какая она есть.

Answer 5

Python wiki имеет список синтаксических анализаторов языка, написанных на Python.