syntax-analysis/example.py at master · Kienyew/syntax-analysis · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
import LL1
from grammar import first, follow
from grammar import NonTerminal
from grammar import Grammar, terminals, non_terminals
from pprint import pprint

# Define the grammar:
#   Expr -> Expr + Term
#   	  | Expr - Term
#   	  | Term
#
#   Term -> Term * Factor
#   	  | Expr / Term
#   	  | Factor
#
#   Factor -> num | ( Expr )


def expr_grammar():
    Expr, Term, Factor = non_terminals('Expr', 'Term', 'Factor')
    plus, minus, times, div, num, lp, rp = terminals(
        '+', '-', '*', '/', 'num', '(', ')')

    G = Grammar(Expr)  # Expr is starting symbol
    G.add_production(Expr, [Expr, plus, Term])
    G.add_production(Expr, [Expr, minus, Term])
    G.add_production(Expr, [Term])
    G.add_production(Term, [Term, times, Factor])
    G.add_production(Term, [Expr, div, Term])
    G.add_production(Term, [Factor])
    G.add_production(Factor, [num])
    G.add_production(Factor, [lp, Expr, rp])
    # pprint(G)

    return G


def parentheses_grammar():
    Start, List, Pair = non_terminals('S', 'List', 'Pair')
    lp, rp = terminals('(', ')')
    G = Grammar(Start)
    G.add_production(Start, [List])
    G.add_production(List, [List, Pair])
    G.add_production(List, [Pair])
    G.add_production(Pair, [lp, Pair, rp])
    G.add_production(Pair, [lp, rp])

    return G

# First and Follow


def first_and_follow():
    G = expr_grammar()
    print(first(Expr, G))   # {(, num}
    print(follow(Expr, G))  # {), /, $, -, +}


# Create LL(1) Parsing Table
def create_ll1_parsing_table():
    S = NonTerminal('S')
    plus, times, a = terminals('+', '*', 'a')
    G = Grammar(S)
    G.add_production(S, [plus, S, S])
    G.add_production(S, [times, S, S])
    G.add_production(S, [a])
    pprint(LL1.construct_parsing_table(G))
    # {(S, *): {S -> * S S},
    #  (S, +): {S -> + S S},
    #  (S, a): {S -> a}}


# Create LR(1) Parsing Table
def create_lr1_parsing_table():
    import LR1
    from misc import generate_automaton_graphviz

    G = parentheses_grammar()
    canonical_set = LR1.construct_canonical_set(G)
    pt = LR1.construct_parsing_table(G)
    # pprint(canonical_set)  # CanonicalSet(...)
    # pprint(pt)  # ParsingTable(...)
    print(generate_automaton_graphviz(pt))


# Create LALR(1) Parsing Table
def create_lalr1_parsing_table():
    import LALR1
    from misc import generate_automaton_graphviz
    G = parentheses_grammar()
    pt = LALR1.construct_parsing_table(G)
    print(generate_automaton_graphviz(pt))

create_lalr1_parsing_table()