Modify the config file if necessary and then execute:
python demo.py --config=<config> --text=<text>
The image of the output parse tree will be saved in out/parse-tree.svg. (This behavior can be changed in demo.py.)
Take the regular expression (a|b)*abb for example.
-
Create an NFA from the regular expression:
import ptree from ptree.lexer.regex import Regex, RegexEngine regex = Regex(name='(a|b)*abb', pattern='(a|b)*abb') engine = RegexEngine() nfa = engine.parse(regex) ptree.render(nfa, directory='out', name='nfa', output_format='svg')
-
Convert the NFA to a DFA:
dfa = nfa.to_dfa() ptree.render(dfa, directory='out', name='dfa', output_format='svg')
Take the regular expressions a*b , a, abb for example.
-
Create three NFAs from the regular expressions.
import ptree from ptree.lexer.regex import Regex, RegexEngine regexes = [ Regex(name='a*b ', pattern='a*b '), Regex(name='a', pattern='a'), Regex(name='abb', pattern='abb') ] engine = RegexEngine() nfas = [engine.parse(regex) for regex in regexes] for i, nfa in enumerate(nfas): ptree.render(nfa, directory='out', name=f'nfa-{i}', output_format='svg')
-
Merge the NFAs.
from ptree.lexer.nfa import NFA nfa = NFA.union(nfas) ptree.render(nfa, directory='out', name='nfa', output_format='svg')
-
Convert the NFA to DFA.
dfa = nfa.to_dfa() ptree.render(dfa, directory='out', name='dfa', output_format='svg')
-
Create a lexer from the config file.
The config file used in this example is:
nonterminal_symbols: terminal_symbols: COMMENT: '(//[^\n]*)|(/\*([^\*]|(\*)*[^\*/])*(\*)*\*/)' KEYWORD: 'auto|short|int|long|float|double|char|struct|union|enum|typedef|const|unsigned|signed|extern|register|static|volatile|void|if|else|switch|case|for|do|while|goto|continue|break|default|sizeof|return|using|namespace' IDENTIFIER: '[A-Za-z_][A-Za-z0-9_]*' INTEGER: '[0-9] ' FLOAT: '[0-9] \.[0-9] ' COMPARISON: '==|>|<|>=|<=|!=' LSTREAM: '<<' RSTREAM: '>>' LP: '\(' RP: '\)' LB: '{' RB: '}' COMMA: ',' SEMICOLON: ';' LSB: '\[' RSB: '\]' ASSIGN_OP: '=' ADD_OP: '\ ' SUB_OP: '\-' MULT_OP: '\*' DIV_OP: '/' MOD_OP: '%' POWER_OP: '\^' AND_OP: '&&' OR_OP: '\|\|' NOT_OP: '!' SPACE: '[ \t\n\r] ' ignored_symbols: ? SPACE ? COMMENT start_symbol: production_rules:
import ptree config = ptree.load_config('config.yaml') grammar = ptree.Grammar(config) lexer = ptree.Lexer(config, symbol_pool=grammar.symbol_pool)
-
Tokenize the input string.
The input string is:
int main() {int a = a 1; cout << a << endl; return 0;}
tokens = lexer.tokenize('''int main() {int a = a 1; cout << a << endl; return 0;}''') ptree.pprint(tokens)
---- ------------ -------- | | SYMBOL | VALUE | ==== ============ ======== | 1 | KEYWORD | int | ---- ------------ -------- | 2 | IDENTIFIER | main | ---- ------------ -------- | 3 | LP | ( | ---- ------------ -------- | 4 | RP | ) | ---- ------------ -------- | 5 | LB | { | ---- ------------ -------- | 6 | KEYWORD | int | ---- ------------ -------- | 7 | IDENTIFIER | a | ---- ------------ -------- | 8 | ASSIGN_OP | = | ---- ------------ -------- | 9 | IDENTIFIER | a | ---- ------------ -------- | 10 | ADD_OP | | ---- ------------ -------- | 11 | INTEGER | 1 | ---- ------------ -------- | 12 | SEMICOLON | ; | ---- ------------ -------- | 13 | IDENTIFIER | cout | ---- ------------ -------- | 14 | LSTREAM | << | ---- ------------ -------- | 15 | IDENTIFIER | a | ---- ------------ -------- | 16 | LSTREAM | << | ---- ------------ -------- | 17 | IDENTIFIER | endl | ---- ------------ -------- | 18 | SEMICOLON | ; | ---- ------------ -------- | 19 | KEYWORD | return | ---- ------------ -------- | 20 | INTEGER | 0 | ---- ------------ -------- | 21 | SEMICOLON | ; | ---- ------------ -------- | 22 | RB | } | ---- ------------ --------
-
Write a config file (in YAML format).
nonterminal_symbols: ? E ? T ? F terminal_symbols: ' ': '\ ' '-': '\-' '*': '\*' '/': '/' '(': '\(' ')': '\)' 'num': '[0-9] ' ignored_symbols: start_symbol: E production_rules: - E -> E T - E -> E - T - E -> T - T -> T * F - T -> T / F - T -> F - F -> num - F -> ( E )
-
Generate the parse table.
import ptree config = ptree.load_config('config.yaml') grammar = ptree.Grammar(config) grammar.init() parser = ptree.Parser(grammar) ptree.pprint(grammar.parse_table)
---- ---------------------------------------------- -------------- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | ACTION | GOTO | STATE | ---- ----- ----- ----- ----- ---- ----- ----- ----- ---- ---- ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | | - | * | / | ( | ) | num | $ | E | T | F | | ---- ----- ----- ----- ----- ---- ----- ----- ----- ---- ---- ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 0 | | | | | s1 | | s2 | | 4 | 5 | 3 | {F -> . ( E ), *; F -> . num, *; T -> . F, $; E -> . E - T, -; _S -> . E, $; E -> . T, $; T -> . F, /; F -> . ( E ), $; T -> . T * F, $; T -> . T / F, $; E -> . E T, -; F -> . num, $; T -> . T * F, /; E -> . E - T, $; T -> . F, ; E -> . E T, $; F -> . ( E ), /; E -> . T, ; T -> . F, -; T -> . T * F, ; T -> . T / F, ; T -> . T / F, /; F -> . ( E ), ; F -> . num, ; T -> . T / F, -; F -> . num, /; T -> . F, *; E -> . E - T, ; T -> . T * F, -; F -> . num, -; E -> . T, -; E -> . E T, ; F -> . ( E ), -; T -> . T * F, *; T -> . T / F, *} | ---- ----- ----- ----- ----- ---- ----- ----- ----- ---- ---- ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 1 | | | | | s6 | | s7 | | 8 | 10 | 9 | {F -> . ( E ), *; F -> . num, *; E -> . E - T, -; T -> . F, /; F -> ( . E ), /; E -> . E T, -; T -> . T / F, ); E -> . T, ); F -> . ( E ), ); F -> ( . E ), ; T -> . T * F, ); T -> . T * F, /; F -> . num, ); T -> . T * F, *; T -> . F, ; F -> . ( E ), /; E -> . E - T, ); E -> . T, ; E -> . E T, ); T -> . F, -; T -> . T * F, ; F -> ( . E ), *; F -> ( . E ), -; T -> . T / F, ; T -> . T / F, /; F -> . ( E ), ; F -> . num, ; T -> . T / F, -; F -> . num, /; T -> . F, *; E -> . E - T, ; T -> . T * F, -; F -> . num, -; F -> ( . E ), $; E -> . T, -; E -> . E T, ; F -> . ( E ), -; T -> . F, ); T -> . T / F, *} | ---- ----- ----- ----- ----- ---- ----- ----- ----- ---- ---- ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 2 | r7 | r7 | r7 | r7 | | | | r7 | | | | {F -> num . , -; F -> num . , ; F -> num . , /; F -> num . , *; F -> num . , $} | ---- ----- ----- ----- ----- ---- ----- ----- ----- ---- ---- ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 3 | r6 | r6 | r6 | r6 | | | | r6 | | | | {T -> F . , -; T -> F . , ; T -> F . , /; T -> F . , *; T -> F . , $} | ---- ----- ----- ----- ----- ---- ----- ----- ----- ---- ---- ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 4 | s12 | s11 | | | | | | acc | | | | {E -> E . - T, -; E -> E . - T, $; E -> E . T, ; _S -> E . , $; E -> E . T, -; E -> E . T, $; E -> E . - T, } | ---- ----- ----- ----- ----- ---- ----- ----- ----- ---- ---- ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 5 | r3 | r3 | s14 | s13 | | | | r3 | | | | {T -> T . / F, -; T -> T . / F, ; E -> T . , ; T -> T . * F, /; T -> T . * F, ; E -> T . , -; E -> T . , $; T -> T . / F, /; T -> T . / F, *; T -> T . / F, $; T -> T . * F, *; T -> T . * F, $; T -> T . * F, -} | ---- ----- ----- ----- ----- ---- ----- ----- ----- ---- ---- ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 6 | | | | | s6 | | s7 | | 15 | 10 | 9 | {F -> ( . E ), ); F -> . ( E ), *; F -> . num, *; E -> . E - T, -; T -> . F, /; F -> ( . E ), /; E -> . E T, -; T -> . T / F, ); E -> . T, ); F -> . ( E ), ); F -> ( . E ), ; T -> . T * F, ); T -> . T * F, /; F -> . num, ); T -> . T * F, *; T -> . F, ; F -> . ( E ), /; E -> . E - T, ); E -> . T, ; E -> . E T, ); T -> . F, -; T -> . T * F, ; F -> ( . E ), *; F -> ( . E ), -; T -> . T / F, ; T -> . T / F, /; F -> . ( E ), ; F -> . num, ; T -> . T / F, -; F -> . num, /; T -> . F, *; E -> . E - T, ; T -> . T * F, -; F -> . num, -; E -> . T, -; E -> . E T, ; F -> . ( E ), -; T -> . F, ); T -> . T / F, *} | ---- ----- ----- ----- ----- ---- ----- ----- ----- ---- ---- ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 7 | r7 | r7 | r7 | r7 | | r7 | | | | | | {F -> num . , ); F -> num . , -; F -> num . , ; F -> num . , /; F -> num . , *} | ---- ----- ----- ----- ----- ---- ----- ----- ----- ---- ---- ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 8 | s16 | s18 | | | | s17 | | | | | | {E -> E . T, ); F -> ( E . ), ; E -> E . - T, ); F -> ( E . ), -; E -> E . - T, -; E -> E . T, ; F -> ( E . ), *; F -> ( E . ), $; F -> ( E . ), /; E -> E . T, -; E -> E . - T, } | ---- ----- ----- ----- ----- ---- ----- ----- ----- ---- ---- ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 9 | r6 | r6 | r6 | r6 | | r6 | | | | | | {T -> F . , -; T -> F . , ; T -> F . , ); T -> F . , /; T -> F . , *} | ---- ----- ----- ----- ----- ---- ----- ----- ----- ---- ---- ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 10 | r3 | r3 | s20 | s19 | | r3 | | | | | | {T -> T . / F, -; T -> T . / F, ; E -> T . , ; T -> T . * F, /; T -> T . * F, ; T -> T . * F, -; E -> T . , -; T -> T . / F, /; T -> T . / F, *; T -> T . * F, *; E -> T . , ); T -> T . * F, ); T -> T . / F, )} | ---- ----- ----- ----- ----- ---- ----- ----- ----- ---- ---- ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 11 | | | | | s1 | | s2 | | | 21 | 3 | {F -> . ( E ), *; F -> . num, *; T -> . F, $; E -> E - . T, ; T -> . F, /; F -> . ( E ), $; T -> . T * F, $; T -> . T / F, $; F -> . num, $; T -> . T * F, /; E -> E - . T, -; T -> . F, ; F -> . ( E ), /; T -> . F, -; T -> . T * F, ; T -> . T / F, ; T -> . T / F, /; F -> . ( E ), ; F -> . num, ; E -> E - . T, $; T -> . T / F, -; F -> . num, /; T -> . F, *; T -> . T * F, -; F -> . num, -; F -> . ( E ), -; T -> . T * F, *; T -> . T / F, *} | ---- ----- ----- ----- ----- ---- ----- ----- ----- ---- ---- ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 12 | | | | | s1 | | s2 | | | 22 | 3 | {F -> . ( E ), *; F -> . num, *; T -> . F, $; T -> . F, /; F -> . ( E ), $; T -> . T * F, $; T -> . T / F, $; E -> E . T, ; F -> . num, $; T -> . T * F, /; T -> . F, ; F -> . ( E ), /; E -> E . T, -; T -> . F, -; T -> . T * F, ; T -> . T / F, ; T -> . T / F, /; F -> . ( E ), ; F -> . num, ; T -> . T / F, -; F -> . num, /; T -> . F, *; T -> . T * F, -; F -> . num, -; E -> E . T, $; F -> . ( E ), -; T -> . T * F, *; T -> . T / F, *} | ---- ----- ----- ----- ----- ---- ----- ----- ----- ---- ---- ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 13 | | | | | s1 | | s2 | | | | 23 | {T -> T / . F, ; F -> . ( E ), *; F -> . ( E ), /; T -> T / . F, /; T -> T / . F, *; F -> . num, *; F -> . num, /; F -> . num, $; T -> T / . F, $; F -> . num, -; T -> T / . F, -; F -> . num, ; F -> . ( E ), ; F -> . ( E ), -; F -> . ( E ), $} | ---- ----- ----- ----- ----- ---- ----- ----- ----- ---- ---- ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 14 | | | | | s1 | | s2 | | | | 24 | {F -> . ( E ), *; T -> T * . F, /; T -> T * . F, *; F -> . num, /; F -> . num, *; F -> . ( E ), /; T -> T * . F, $; F -> . num, $; F -> . ( E ), $; F -> . num, -; T -> T * . F, -; F -> . ( E ), ; F -> . ( E ), -; T -> T * . F, ; F -> . num, } | ---- ----- ----- ----- ----- ---- ----- ----- ----- ---- ---- ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 15 | s16 | s18 | | | | s25 | | | | | | {E -> E . T, ); F -> ( E . ), ; E -> E . - T, ); F -> ( E . ), -; E -> E . - T, -; E -> E . T, ; F -> ( E . ), *; F -> ( E . ), ); F -> ( E . ), /; E -> E . T, -; E -> E . - T, } | ---- ----- ----- ----- ----- ---- ----- ----- ----- ---- ---- ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 16 | | | | | s6 | | s7 | | | 26 | 9 | {F -> . ( E ), *; F -> . num, *; T -> . F, /; E -> E . T, ; T -> . T / F, ); F -> . ( E ), ); T -> . T * F, ); T -> . T * F, /; F -> . num, ); T -> . T * F, *; T -> . F, ; F -> . ( E ), /; E -> E . T, -; F -> . ( E ), -; T -> . F, -; T -> . T * F, ; T -> . T / F, ; T -> . T / F, /; F -> . ( E ), ; F -> . num, ; T -> . T / F, -; F -> . num, /; T -> . F, *; T -> . T * F, -; F -> . num, -; E -> E . T, ); T -> . F, ); T -> . T / F, *} | ---- ----- ----- ----- ----- ---- ----- ----- ----- ---- ---- ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 17 | r8 | r8 | r8 | r8 | | | | r8 | | | | {F -> ( E ) . , $; F -> ( E ) . , /; F -> ( E ) . , ; F -> ( E ) . , -; F -> ( E ) . , *} | ---- ----- ----- ----- ----- ---- ----- ----- ----- ---- ---- ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 18 | | | | | s6 | | s7 | | | 27 | 9 | {F -> . ( E ), *; F -> . num, *; E -> E - . T, ; T -> . F, /; T -> . T / F, ); F -> . ( E ), ); T -> . T * F, ); T -> . T * F, /; F -> . num, ); T -> . T * F, *; E -> E - . T, -; T -> . F, ; F -> . ( E ), /; T -> . F, -; T -> . T * F, ; T -> . T / F, ; T -> . T / F, /; F -> . ( E ), ; F -> . num, ; T -> . T / F, -; F -> . num, /; T -> . F, *; T -> . T / F, *; T -> . T * F, -; F -> . num, -; F -> . ( E ), -; T -> . F, ); E -> E - . T, )} | ---- ----- ----- ----- ----- ---- ----- ----- ----- ---- ---- ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 19 | | | | | s6 | | s7 | | | | 28 | {T -> T / . F, ; F -> . ( E ), *; F -> . ( E ), /; T -> T / . F, /; T -> T / . F, *; F -> . num, *; F -> . num, /; F -> . ( E ), ); F -> . num, -; T -> T / . F, -; F -> . num, ); T -> T / . F, ); F -> . ( E ), ; F -> . ( E ), -; F -> . num, } | ---- ----- ----- ----- ----- ---- ----- ----- ----- ---- ---- ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 20 | | | | | s6 | | s7 | | | | 29 | {F -> . ( E ), *; T -> T * . F, /; T -> T * . F, *; F -> . num, /; F -> . num, *; F -> . ( E ), /; F -> . ( E ), ); F -> . num, -; T -> T * . F, ); F -> . num, ); T -> T * . F, -; F -> . ( E ), ; F -> . ( E ), -; T -> T * . F, ; F -> . num, } | ---- ----- ----- ----- ----- ---- ----- ----- ----- ---- ---- ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 21 | r2 | r2 | s14 | s13 | | | | r2 | | | | {T -> T . / F, -; T -> T . / F, ; E -> E - T . , ; T -> T . * F, /; T -> T . * F, ; T -> T . / F, /; T -> T . / F, *; E -> E - T . , -; T -> T . / F, $; T -> T . * F, *; E -> E - T . , $; T -> T . * F, $; T -> T . * F, -} | ---- ----- ----- ----- ----- ---- ----- ----- ----- ---- ---- ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 22 | r1 | r1 | s14 | s13 | | | | r1 | | | | {T -> T . / F, -; E -> E T . , -; E -> E T . , $; T -> T . / F, ; T -> T . * F, /; T -> T . * F, ; T -> T . * F, -; T -> T . / F, /; T -> T . / F, *; T -> T . / F, $; T -> T . * F, *; T -> T . * F, $; E -> E T . , } | ---- ----- ----- ----- ----- ---- ----- ----- ----- ---- ---- ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 23 | r5 | r5 | r5 | r5 | | | | r5 | | | | {T -> T / F . , $; T -> T / F . , *; T -> T / F . , -; T -> T / F . , ; T -> T / F . , /} | ---- ----- ----- ----- ----- ---- ----- ----- ----- ---- ---- ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 24 | r4 | r4 | r4 | r4 | | | | r4 | | | | {T -> T * F . , *; T -> T * F . , $; T -> T * F . , -; T -> T * F . , /; T -> T * F . , } | ---- ----- ----- ----- ----- ---- ----- ----- ----- ---- ---- ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 25 | r8 | r8 | r8 | r8 | | r8 | | | | | | {F -> ( E ) . , /; F -> ( E ) . , ); F -> ( E ) . , ; F -> ( E ) . , -; F -> ( E ) . , *} | ---- ----- ----- ----- ----- ---- ----- ----- ----- ---- ---- ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 26 | r1 | r1 | s20 | s19 | | r1 | | | | | | {T -> T . / F, -; E -> E T . , -; T -> T . / F, ; T -> T . * F, /; T -> T . * F, ; T -> T . * F, -; E -> E T . , ); T -> T . / F, /; T -> T . / F, *; T -> T . * F, *; E -> E T . , ; T -> T . * F, ); T -> T . / F, )} | ---- ----- ----- ----- ----- ---- ----- ----- ----- ---- ---- ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 27 | r2 | r2 | s20 | s19 | | r2 | | | | | | {T -> T . / F, -; T -> T . / F, ; E -> E - T . , ; T -> T . * F, /; T -> T . * F, ; T -> T . * F, -; T -> T . / F, /; T -> T . / F, *; E -> E - T . , ); E -> E - T . , -; T -> T . * F, *; T -> T . * F, ); T -> T . / F, )} | ---- ----- ----- ----- ----- ---- ----- ----- ----- ---- ---- ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 28 | r5 | r5 | r5 | r5 | | r5 | | | | | | {T -> T / F . , *; T -> T / F . , ); T -> T / F . , -; T -> T / F . , ; T -> T / F . , /} | ---- ----- ----- ----- ----- ---- ----- ----- ----- ---- ---- ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 29 | r4 | r4 | r4 | r4 | | r4 | | | | | | {T -> T * F . , *; T -> T * F . , -; T -> T * F . , ); T -> T * F . , /; T -> T * F . , } | ---- ----- ----- ----- ----- ---- ----- ----- ----- ---- ---- ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -
Tokenize the input string.
The input string is
3*(6 (4/2)-5) 8.lexer = ptree.Lexer(config, symbol_pool=grammar.symbol_pool) tokens = lexer.tokenize('3*(6 (4/2)-5) 8') ptree.pprint(tokens)
---- -------- ------- | | SYMBOL | VALUE | ==== ======== ======= | 1 | num | 3 | ---- -------- ------- | 2 | * | * | ---- -------- ------- | 3 | ( | ( | ---- -------- ------- | 4 | num | 6 | ---- -------- ------- | 5 | | | ---- -------- ------- | 6 | ( | ( | ---- -------- ------- | 7 | num | 4 | ---- -------- ------- | 8 | / | / | ---- -------- ------- | 9 | num | 2 | ---- -------- ------- | 10 | ) | ) | ---- -------- ------- | 11 | - | - | ---- -------- ------- | 12 | num | 5 | ---- -------- ------- | 13 | ) | ) | ---- -------- ------- | 14 | | | ---- -------- ------- | 15 | num | 8 | ---- -------- ------- -
Generate the parse tree.
parse_tree = parser.parse(tokens) ptree.render(parse_tree, directory='out', name='parse-tree', output_format='svg')
-
Get the predefined grammar.
1. S'->S 2. S->CβBA 3. A->Aαβ 4. A->αβ 5. B->C 6. B->Dβ 7. C->α 8. D->α -
Write a config file (in YAML format).
nonterminal_symbols: # ? name ? A ? B ? C ? D ? S terminal_symbols: # name: regex α: a β: b ignored_symbols: start_symbol: S production_rules: # - left part -> right part - S -> C β B A - A -> A α β - A -> α β - B -> C - B -> D β - C -> α - D -> α
-
Generate the parse table.
import ptree config = ptree.load_config('config.yaml') grammar = ptree.Grammar(config) grammar.init() parser = ptree.Parser(grammar) ptree.pprint(grammar.parse_table)
---- ----------------- ------------------- ----------------------------------------------------------------------------------------- | | ACTION | GOTO | STATE | ---- ----- ----- ----- --- --- --- --- --- ----------------------------------------------------------------------------------------- | | α | β | $ | A | B | C | D | S | | ---- ----- ----- ----- --- --- --- --- --- ----------------------------------------------------------------------------------------- | 0 | s1 | | | | | 3 | | 2 | {C -> . α, β; _S -> . S, $; S -> . C β B A, $} | ---- ----- ----- ----- --- --- --- --- --- ----------------------------------------------------------------------------------------- | 1 | | r6 | | | | | | | {C -> α . , β} | ---- ----- ----- ----- --- --- --- --- --- ----------------------------------------------------------------------------------------- | 2 | | | acc | | | | | | {_S -> S . , $} | ---- ----- ----- ----- --- --- --- --- --- ----------------------------------------------------------------------------------------- | 3 | | s4 | | | | | | | {S -> C . β B A, $} | ---- ----- ----- ----- --- --- --- --- --- ----------------------------------------------------------------------------------------- | 4 | s5 | | | | 6 | 8 | 7 | | {C -> . α, α; S -> C β . B A, $; D -> . α, β; B -> . D β, α; B -> . C, α} | ---- ----- ----- ----- --- --- --- --- --- ----------------------------------------------------------------------------------------- | 5 | r6 | r7 | | | | | | | {C -> α . , α; D -> α . , β} | ---- ----- ----- ----- --- --- --- --- --- ----------------------------------------------------------------------------------------- | 6 | s10 | | | 9 | | | | | {A -> . A α β, $; A -> . A α β, α; A -> . α β, $; S -> C β B . A, $; A -> . α β, α} | ---- ----- ----- ----- --- --- --- --- --- ----------------------------------------------------------------------------------------- | 7 | | s11 | | | | | | | {B -> D . β, α} | ---- ----- ----- ----- --- --- --- --- --- ----------------------------------------------------------------------------------------- | 8 | r4 | | | | | | | | {B -> C . , α} | ---- ----- ----- ----- --- --- --- --- --- ----------------------------------------------------------------------------------------- | 9 | s12 | | r1 | | | | | | {A -> A . α β, $; A -> A . α β, α; S -> C β B A . , $} | ---- ----- ----- ----- --- --- --- --- --- ----------------------------------------------------------------------------------------- | 10 | | s13 | | | | | | | {A -> α . β, $; A -> α . β, α} | ---- ----- ----- ----- --- --- --- --- --- ----------------------------------------------------------------------------------------- | 11 | r5 | | | | | | | | {B -> D β . , α} | ---- ----- ----- ----- --- --- --- --- --- ----------------------------------------------------------------------------------------- | 12 | | s14 | | | | | | | {A -> A α . β, $; A -> A α . β, α} | ---- ----- ----- ----- --- --- --- --- --- ----------------------------------------------------------------------------------------- | 13 | r3 | | r3 | | | | | | {A -> α β . , $; A -> α β . , α} | ---- ----- ----- ----- --- --- --- --- --- ----------------------------------------------------------------------------------------- | 14 | r2 | | r2 | | | | | | {A -> A α β . , $; A -> A α β . , α} | ---- ----- ----- ----- --- --- --- --- --- ----------------------------------------------------------------------------------------- -
Tokenize the input string.
The input string is
abababab.lexer = ptree.Lexer(config, symbol_pool=grammar.symbol_pool) tokens = lexer.tokenize('abababab') ptree.pprint(tokens)
--- -------- ------- | | SYMBOL | VALUE | === ======== ======= | 1 | α | a | --- -------- ------- | 2 | β | b | --- -------- ------- | 3 | α | a | --- -------- ------- | 4 | β | b | --- -------- ------- | 5 | α | a | --- -------- ------- | 6 | β | b | --- -------- ------- | 7 | α | a | --- -------- ------- | 8 | β | b | --- -------- ------- -
Generate the parse tree.
parse_tree = parser.parse(tokens) ptree.render(parse_tree, directory='out', name='parse-tree', output_format='svg')
