मुझे उचित रूबी/पायथन पार्सर जनरेटर

Question

पार्स :: रिकडेसेंट के साथ काम करने वाले पहले पार्सर जेनरेटर और इसके लिए उपलब्ध मार्गदर्शिका/ट्यूटोरियल बहुत अच्छे थे, लेकिन सबसे उपयोगी सुविधा यह है कि यह डिबगिंग टूल था , विशेष रूप से क्षमताओं का पता लगाने ($ RD_TRACE को 1 से सेट करके सक्रिय)। मैं एक पार्सर जनरेटर की तलाश में हूं जो आपको इसके नियमों को डीबग करने में मदद कर सकता है।

बात यह है कि इसे पाइथन या रूबी में लिखा जाना चाहिए, और वर्बोज़ मोड/ट्रेस मोड या बहुत उपयोगी डिबगिंग तकनीकें होंगी।

क्या कोई ऐसे पार्सर जनरेटर को जानता है?

संपादित करें: जब मैंने डिबगिंग कहा, तो मैं डिबगिंग पायथन या रूबी का जिक्र नहीं कर रहा था। मैं पार्सर जनरेटर को डीबग करने का जिक्र कर रहा था, देखिए कि यह हर कदम पर क्या कर रहा है, हर चार इसे पढ़ रहा है, नियमों का मिलान करने की कोशिश कर रहा है। आशा है कि आप बिंदु प्राप्त करें।

BOUNTY संपादित करें: बक्षीस जीतने के लिए, कृपया एक पार्सर जनरेटर फ्रेमवर्क दिखाएं, और इसकी कुछ डीबगिंग सुविधाओं को चित्रित करें। मैं दोहराता हूं, मुझे पीडीबी में दिलचस्पी नहीं है, लेकिन पार्सर के डीबगिंग फ्रेमवर्क में। इसके अलावा, कृपया treetop का जिक्र मत करो। मुझे इसमें रूचि नहीं है।

Answer 1

पायथन डीबग करने के लिए एक बहुत ही आसान भाषा है। आप सिर्फ पीडीबी pdb.settrace() आयात कर सकते हैं।

हालांकि, इन पार्सर जेनरेटर अच्छी तरह से अच्छी डीबगिंग सुविधाओं के साथ आते हैं।

http://www.antlr.org/

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

http://pyparsing.wikispaces.com/

जवाब में इनाम के लिए

यहाँ कार्रवाई में प्लाई डिबगिंग है।

स्रोत कोड

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

पायथन विकी में पाइथन में लिखी गई भाषा पार्सर्स का list है।

Answer 3

मैं अपने डिबगिंग सुविधाओं के बारे में कुछ नहीं पता है, लेकिन मैं है PyParsing के बारे में अच्छी बातें सुनी।

http://pyparsing.wikispaces.com/

Answer 4

मैं इनाम पहले से ही दावा किया गया है पता है, लेकिन यहां एक बराबर पार्सर pyparsing में लिखा (प्लस समारोह के लिए समर्थन शून्य या अधिक अल्पविराम delimted तर्क के साथ कॉल) है:

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 

इस उत्पादन देता है:

अब

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

और हम पहले टेस्ट (इनपुट स्ट्रिंग और एक साधारण स्तंभ शासक दिखाते हैं) Reparse:

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']]]]] 

डिबगिंग के लिए, हम इस कोड को जोड़ना

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

इस उत्पादन देते :

123456789
    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'] 

पाइपरिंग पैकर पार्सिंग का भी समर्थन करता है, एक प्रकार पार्स-टाइम ज्ञापन (here पैकिंग के बारे में और पढ़ें)। यहाँ एक ही पार्स अनुक्रम है, लेकिन packrat के साथ सक्षम:

same parse, but with packrat parsing enabled 
123456789
    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 5

ANTLR ऊपर लाभ, मानव पठनीय और समझा जा सकता कोड उत्पन्न करने के लिए है, क्योंकि यह है (एक बहुत परिष्कृत और शक्तिशाली) ऊपर से नीचे पार्सर, ताकि आप इसे माध्यम से एक नियमित रूप से डिबगर साथ कदम और देख सकते हैं कि यह वास्तव में कर रहा है।

यही कारण है कि यह मेरी पसंद का पार्सर जनरेटर है।

नीचे ऊपर प्लाई की तरह पार्सर जनरेटर नुकसान कि बड़े व्याकरण के लिए यह लगभग को समझने के लिए असंभव है क्या डिबगिंग आउटपुट वास्तव में इसका मतलब है और क्यों पार्स तालिका है यह है की तरह है।