!type Examples\c-grammar.g

!cat Examples/arith.g

"""
Explanation: Implementing an LR-Table-Generator
A Grammar for Grammars
As the goal is to generate an LR-table-generator we first need to implement a parser for context free grammars.
The file arith.g contains an example grammar that describes arithmetic expressions.
End of explanation
"""


!cat Pure.g4

"""
Explanation: We use <span style="font-variant:small-caps;">Antlr</span> to develop a parser for context free grammars.  The pure grammar used to parse context free grammars is stored in the file Pure.g4.  It is similar to the grammar that we have already used to implement Earley's algorithm, but allows additionally the use of the operator |, so that all grammar rules that define a variable can be combined in one rule.
End of explanation
"""


!cat -n Grammar.g4

"""
Explanation: The annotated grammar is stored in the file Grammar.g4.
The parser will return a list of grammar rules, where each rule of the form
$$ a \rightarrow \beta $$
is stored as the tuple (a,) + 𝛽.
End of explanation
"""


!antlr4 -Dlanguage=Python3 Grammar.g4

from GrammarLexer  import GrammarLexer
from GrammarParser import GrammarParser
import antlr4

"""
Explanation: We start by generating both scanner and parser.
End of explanation
"""


class GrammarRule:
    def __init__(self, variable, body):
        self.mVariable = variable
        self.mBody     = body
        
    def __eq__(self, other):
        return isinstance(other, GrammarRule)    and \
               self.mVariable == other.mVariable and \
               self.mBody     == other.mBody
    
    def __ne__(self, other):
        return not self.__eq__(other)
    
    def __hash__(self):
        return hash(self.__repr__())
    
    def __repr__(self):
        return f'{self.mVariable} → {" ".join(self.mBody)}'

"""
Explanation: The Class GrammarRule
The class GrammarRule is used to store a single grammar rule.  As we have to use objects of type GrammarRule as keys in a dictionary later, we have to provide the methods __eq__, __ne__, and __hash__.
End of explanation
"""


def parse_grammar(filename):
    input_stream  = antlr4.FileStream(filename, encoding="utf-8")
    lexer         = GrammarLexer(input_stream)
    token_stream  = antlr4.CommonTokenStream(lexer)
    parser        = GrammarParser(token_stream)
    grammar       = parser.start()
    return [GrammarRule(head, tuple(body)) for head, *body in grammar.g]

grammar = parse_grammar('Examples/c-grammar.g')
grammar

"""
Explanation: The function parse_grammar takes a string filename as its argument and returns the grammar that is stored in the specified file.  The grammar is represented as list of rules.  Each rule is represented as a tuple.  The example below will clarify this structure.
End of explanation
"""


def is_var(name):
    return name[0] != "'" and name.islower()

"""
Explanation: Given a string name, which is either a variable, a token, or a literal, the function is_var checks whether name is a variable.  The function can distinguish variable names from tokens and literals because variable names consist only of lower case letters, while tokens are all uppercase and literals start with the character "'".
End of explanation
"""


def collect_variables(Rules):
    Variables = set()
    for rule in Rules:
        Variables.add(rule.mVariable)
        for item in rule.mBody:
            if is_var(item):
                Variables.add(item)
    return Variables

"""
Explanation: Given a list Rules of GrammarRules, the function collect_variables(Rules) returns the set of all variables occuring in Rules.
End of explanation
"""


def collect_tokens(Rules):
    Tokens = set()
    for rule in Rules:
        for item in rule.mBody:
            if not is_var(item):
                Tokens.add(item)
    return Tokens

"""
Explanation: Given a set Rules of GrammarRules, the function collect_tokens(Rules) returns the set of all tokens and literals occuring in Rules.
End of explanation
"""


class ExtendedMarkedRule():
    def __init__(self, variable, alpha, beta, follow):
        self.mVariable = variable
        self.mAlpha    = alpha
        self.mBeta     = beta
        self.mFollow   = follow
        
    def __eq__(self, other):
        return isinstance(other, ExtendedMarkedRule) and \
               self.mVariable == other.mVariable     and \
               self.mAlpha    == other.mAlpha        and \
               self.mBeta     == other.mBeta         and \
               self.mFollow   == other.mFollow
    
    def __ne__(self, other):
        return not self.__eq__(other)
    
    def __hash__(self):
        return hash(self.mVariable) + \
               hash(self.mAlpha)    + \
               hash(self.mBeta)     + \
               hash(self.mFollow)
    
    def __repr__(self):
        alphaStr  = ' '.join(self.mAlpha)
        betaStr   = ' '.join(self.mBeta)
        if len(self.mFollow) > 1:
            followStr = '{' + ','.join(self.mFollow) + '}'
        else:
            followStr = ','.join(self.mFollow)
        return f'{self.mVariable} → {alphaStr} • {betaStr}: {followStr}'

"""
Explanation: Extended Marked Rules
The class ExtendedMarkedRule stores a single marked rule of the form
$$ v \rightarrow \alpha \bullet \beta : L $$
where the variable $v$ is stored in the member variable mVariable, while $\alpha$ and $\beta$ are stored in the variables mAlphaand mBeta respectively.  The set of follow tokens $L$ is stored in the variable mFollow. These variables are assumed to contain tuples of grammar symbols.  A grammar symbol is either
- a variable,
- a token, or
- a literal, i.e. a string enclosed in single quotes.
Later, we need to maintain sets of marked rules to represent states.  Therefore, we have to define the methods __eq__, __ne__, and __hash__.
End of explanation
"""


def is_complete(self):
    return len(self.mBeta) == 0

ExtendedMarkedRule.is_complete = is_complete
del is_complete

"""
Explanation: Given an extended marked rule self, the function is_complete checks, whether the extended marked rule self has the form
$$ c \rightarrow \alpha\; \bullet: L,$$
i.e. it checks, whether the $\bullet$ is at the end of the grammar rule.
End of explanation
"""


def symbol_after_dot(self):
    if len(self.mBeta) > 0:
        return self.mBeta[0]
    return None

ExtendedMarkedRule.symbol_after_dot = symbol_after_dot
del symbol_after_dot

"""
Explanation: Given an extended marked rule self of the form
$$ c \rightarrow \alpha \bullet X\, \delta: L, $$
the function symbol_after_dot returns the symbol $X$. If there is no symbol after the $\bullet$, the method returns None.
End of explanation
"""


def is_var(name):
    return name[0] != "'" and name.islower()

"""
Explanation: Given a grammar symbol name, which is either a variable, a token, or a literal, the function is_var checks whether name is a variable.  The function can distinguish variable names from tokens and literals because variable names consist only of lower case letters, while tokens are all uppercase and literals start with the character "'".
End of explanation
"""


def next_var(self):
    if len(self.mBeta) > 0:
        var = self.mBeta[0]
        if is_var(var):
            return var
    return None

ExtendedMarkedRule.next_var = next_var
del next_var

"""
Explanation: Given an extended marked rule, this function returns the variable following the dot.  If there is no variable following the dot, the function returns None.
End of explanation
"""


def move_dot(self):
    return ExtendedMarkedRule(self.mVariable, 
                              self.mAlpha + (self.mBeta[0],), 
                              self.mBeta[1:],
                              self.mFollow)

ExtendedMarkedRule.move_dot = move_dot
del move_dot

"""
Explanation: The function move_dot(self) transforms an extended marked rule  of the form 
$$ c \rightarrow \alpha \bullet X\, \beta: L $$
into an extended marked rule of the form
$$ c \rightarrow \alpha\, X \bullet \beta: L, $$
i.e. the $\bullet$ is moved over the next symbol.  Invocation of this method assumes that there is a symbol
following the $\bullet$.
End of explanation
"""


def to_rule(self):
    return GrammarRule(self.mVariable, self.mAlpha + self.mBeta)

ExtendedMarkedRule.to_rule = to_rule
del to_rule

"""
Explanation: The function to_rule(self) turns the extended marked rule self into  a GrammarRule, i.e. the extended marked rule
$$ c \rightarrow \alpha \bullet \beta: L $$
is turned into the grammar rule
$$ c \rightarrow \alpha\, \beta. $$
End of explanation
"""


def to_marked_rule(self):
    return MarkedRule(self.mVariable, self.mAlpha, self.mBeta)

ExtendedMarkedRule.to_marked_rule = to_marked_rule
del to_marked_rule

"""
Explanation: The function to_rule(self) turns the extended marked rule self into a MarkedRule, i.e. the extended marked rule
$$ c \rightarrow \alpha \bullet \beta: L $$
is turned into the marked rule
$$ c \rightarrow \alpha\bullet \beta. $$
End of explanation
"""


class MarkedRule():
    def __init__(self, variable, alpha, beta):
        self.mVariable = variable
        self.mAlpha    = alpha
        self.mBeta     = beta
        
    def __eq__(self, other):
        return isinstance(other, MarkedRule)     and \
               self.mVariable == other.mVariable and \
               self.mAlpha    == other.mAlpha    and \
               self.mBeta     == other.mBeta     
    
    def __ne__(self, other):
        return not self.__eq__(other)
    
    def __hash__(self):
        return hash(self.mVariable) + \
               hash(self.mAlpha)    + \
               hash(self.mBeta)     
    
    def __repr__(self):
        alphaStr  = ' '.join(self.mAlpha)
        betaStr   = ' '.join(self.mBeta)
        return f'{self.mVariable} → {alphaStr} • {betaStr}'

"""
Explanation: The class MarkedRule is similar to the class ExtendedMarkedRule but does not have the follow set.
End of explanation
"""


def combine_rules(M):
    Result = set()
    Core   = set()
    for emr1 in M:
        Follow = set()
        core1 = emr1.to_marked_rule()
        if core1 in Core:
            continue
        Core.add(core1)
        for emr2 in M:
            core2 = emr2.to_marked_rule()
            if core1 == core2:
                Follow |= emr2.mFollow
        new_emr = ExtendedMarkedRule(core1.mVariable, core1.mAlpha, core1.mBeta, frozenset(Follow))
        Result.add(new_emr)
    return frozenset(Result)

"""
Explanation: Given a set of extended marked rules M, the function combine_rule combines those extended marked ruless that have the same core:  If 
$$ a \rightarrow \beta \bullet \gamma : L $$
is an extended marked rule, then its core is defined as the marked rule
$$ a \rightarrow \beta \bullet \gamma. $$
If $a \rightarrow \beta \bullet \gamma : L_1$ and $a \rightarrow \beta \bullet \gamma : L_2$ are two extended marked rules, then they can be combined into the rule
$$ a \rightarrow \beta \bullet \gamma : L_1\cup L_2 $$
End of explanation
"""


class Grammar():
    def __init__(self, Rules):
        self.mRules      = Rules
        self.mStart      = Rules[0].mVariable
        self.mVariables  = collect_variables(Rules)
        self.mTokens     = collect_tokens(Rules)
        self.mStates     = set()
        self.mStateNames = {}
        self.mConflicts  = False
        self.mVariables.add('ŝ')
        self.mTokens.add('$')
        self.mRules.append(GrammarRule('ŝ', (self.mStart, ))) # augmenting
        self.compute_tables()

"""
Explanation: LR-Table-Generation
The class Grammar represents a context free grammar.  It stores a list of the GrammarRules of the given grammar.
Each grammar rule of the form
$$ a \rightarrow \beta $$
The start symbol is assumed to be the variable on the left hand side of the first rule. The grammar is augmented with the rule
$$ \widehat{s} \rightarrow s. $$
Here $s$ is the start variable of the given grammar and $\widehat{s}$ is a new variable that is the start variable of the augmented grammar. The symbol $ denotes the end of input.  The non-obvious member variables of the class Grammar have the following interpretation
- mStates is the set of all states of the LR-parser.  These states are sets of extended marked rules.
- mStateNamesis a dictionary assigning names of the form s0, s1, $\cdots$, sn to the states stored in 
  mStates.  The functions action and goto will be defined for state names, not for states, because 
  otherwise the table representing these functions would become both huge and unreadable.
- mConflicts is a Boolean variable that will be set to true if the table generation discovers 
  shift/reduce conflicts or reduce/reduce conflicts.
End of explanation
"""


def initialize_dictionary(Variables):
    return { a: set() for a in Variables }

"""
Explanation: Given a set of Variables, the function initialize_dictionary returns a dictionary that assigns the empty set to all variables.
End of explanation
"""


def compute_tables(self):
    self.mFirst  = initialize_dictionary(self.mVariables)
    self.mFollow = initialize_dictionary(self.mVariables)
    self.compute_first()
    self.compute_follow()
    self.compute_rule_names()
    self.all_states()
    self.compute_action_table()
    self.compute_goto_table()
    
Grammar.compute_tables = compute_tables
del compute_tables

"""
Explanation: Given a Grammar, the function compute_tables computes
- the sets First(v) and Follow(v) for every variable v,
- the set of all states of the LR-Parser,
- the action table, and
- the goto table. 
Given a grammar g,
- the set g.mFirst is a dictionary such that g.mFirst[a] = First[a] and
- the set g.mFollow is a dictionary such that g.mFollow[a] = Follow[a] for all variables a.
End of explanation
"""


def compute_rule_names(self):
    self.mRuleNames = {}
    counter = 0
    for rule in self.mRules:
        self.mRuleNames[rule] = 'r' + str(counter)
        counter += 1
        
Grammar.compute_rule_names = compute_rule_names
del compute_rule_names

"""
Explanation: The function compute_rule_names assigns a unique name to each rule of the grammar.  These names are used later
to represent reduce actions in the action table.
End of explanation
"""


def compute_first(self):
    change = True
    while change:
        change = False
        for rule in self.mRules:
            a, body = rule.mVariable, rule.mBody
            first_body = self.first_list(body)
            if not (first_body <= self.mFirst[a]):
                change = True
                self.mFirst[a] |= first_body           
    print('First sets:')
    for v in self.mVariables:
        print(f'First({v}) = {self.mFirst[v]}')
        
Grammar.compute_first = compute_first
del compute_first

"""
Explanation: The function compute_first(self) computes the sets $\texttt{First}(c)$ for all variables $c$ and stores them in the dictionary mFirst.  Abstractly, given a variable $c$ the function $\texttt{First}(c)$ is the set of all tokens that can start a string that is derived from $c$:
$$\texttt{First}(\texttt{c}) := 
  \Bigl{ t \in T \Bigm| \exists \gamma \in (V \cup T)^: \texttt{c} \Rightarrow^ t\,\gamma \Bigr}.
$$
The definition of the function $\texttt{First}()$ is extended to strings from $(V \cup T)^$ as follows:
- $\texttt{FirstList}(\varepsilon) = {}$.
- $\texttt{FirstList}(t \beta) = { t }$  if $t \in T$.
- $\texttt{FirstList}(\texttt{a} \beta) = \left{
       \begin{array}[c]{ll}
         \texttt{First}(\texttt{a}) \cup \texttt{FirstList}(\beta) & \mbox{if $\texttt{a} \Rightarrow^ \varepsilon$;} \
         \texttt{First}(\texttt{a})                                & \mbox{otherwise.}
       \end{array}
       \right.
      $ 
If $\texttt{a}$ is a variable of $G$ and the rules defining $\texttt{a}$ are given as 
$$\texttt{a} \rightarrow \alpha_1 \mid \cdots \mid \alpha_n, $$
then we have
$$\texttt{First}(\texttt{a}) = \bigcup\limits_{i=1}^n \texttt{FirstList}(\alpha_i). $$
The dictionary mFirst that stores this function is computed via a fixed point iteration.
End of explanation
"""


def first_list(self, alpha):
    if len(alpha) == 0:
        return { '' }
    elif is_var(alpha[0]): 
        v, *r = alpha
        return eps_union(self.mFirst[v], self.first_list(r))
    else:
        t = alpha[0]
        return { t }
    
Grammar.first_list = first_list
del first_list

"""
Explanation: Given a tuple of variables and tokens alpha, the function first_list(alpha) computes the function $\texttt{FirstList}(\alpha)$ that has been defined above.  If alpha is nullable, then the result will contain the empty string $\varepsilon = \texttt{''}$.
End of explanation
"""


def eps_union(S, T):
    if '' in S: 
        if '' in T: 
            return S | T
        return (S - { '' }) | T
    return S

"""
Explanation: The arguments S and T of eps_union are sets that contain tokens and, additionally, they might contain the empty string.
End of explanation
"""


def compute_follow(self):
    self.mFollow[self.mStart] = { '$' }
    change = True
    while change:
        change = False
        for rule in self.mRules:
            a, body = rule.mVariable, rule.mBody
            for i in range(len(body)):
                if is_var(body[i]):
                    yi        = body[i]
                    Tail      = self.first_list(body[i+1:])
                    firstTail = eps_union(Tail, self.mFollow[a])
                    if not (firstTail <= self.mFollow[yi]): 
                        change = True
                        self.mFollow[yi] |= firstTail  
    print('Follow sets (note that "$" denotes the end of file):');
    for v in self.mVariables:
        print(f'Follow({v}) = {self.mFollow[v]}')
        
Grammar.compute_follow = compute_follow
del compute_follow

"""
Explanation: Given an augmented grammar $G = \langle V,T,R\cup{\widehat{s} \rightarrow s\,\$}, \widehat{s}\rangle$ 
and a variable $a$, the set of tokens that might follow $a$ is defined as:
$$\texttt{Follow}(a) := 
 \bigl{ t \in \widehat{T} \,\bigm|\, \exists \beta,\gamma \in (V \cup \widehat{T})^: 
                           \widehat{s} \Rightarrow^ \beta \,a\, t\, \gamma 
  \bigr}.
$$
The function compute_follow computes the sets $\texttt{Follow}(a)$ for all variables $a$ via a fixed-point iteration.
End of explanation
"""


def cmp_closure(self, Marked_Rules):
    All_Rules = Marked_Rules
    New_Rules = Marked_Rules
    while True:
        More_Rules = set()
        for rule in New_Rules:
            c = rule.next_var()
            if c == None:
                continue
            delta = rule.mBeta[1:]
            L = rule.mFollow
            for rule in self.mRules:
                head, alpha = rule.mVariable, rule.mBody
                if c == head:
                    newL = frozenset({ x for t in L for x in self.first_list(delta + (t,)) })
                    More_Rules |= { ExtendedMarkedRule(head, (), alpha, newL) }
        if More_Rules <= All_Rules:
            return frozenset(All_Rules)
        New_Rules  = More_Rules - All_Rules
        All_Rules |= New_Rules

Grammar.cmp_closure = cmp_closure
del cmp_closure

"""
Explanation: If $\mathcal{M}$ is a set of extended marked rules, then the closure of $\mathcal{M}$ is the smallest set $\mathcal{K}$ such that
we have the following:
- $\mathcal{M} \subseteq \mathcal{K}$,
- If $a \rightarrow \beta \bullet c\, \delta: L$ is a extended marked rule from 
  $\mathcal{K}$, $c$ is a variable, and $t\in L$ and if, furthermore,
  $c \rightarrow \gamma$ is a grammar rule,
  then the marked rule $c \rightarrow \bullet \gamma: \texttt{First}(\delta\,t)$
  is an element of $\mathcal{K}$:
  $$(a \rightarrow \beta \bullet c\, \delta) \in \mathcal{K} 
         \;\wedge\; 
         (c \rightarrow \gamma) \in R
         \;\Rightarrow\; (c \rightarrow \bullet \gamma: \texttt{First}(\delta\,t)) \in \mathcal{K}
  $$
We define $\texttt{closure}(\mathcal{M}) := \mathcal{K}$.  The function cmp_closure computes this closure for a given set of extended marked rules via a fixed-point iteration.
End of explanation
"""


def goto(self, Marked_Rules, x):
    Result = set()
    for mr in Marked_Rules:
        if mr.symbol_after_dot() == x:
            Result.add(mr.move_dot())
    return combine_rules(self.cmp_closure(Result))

Grammar.goto = goto
del goto

"""
Explanation: Given a set of extended marked rules $\mathcal{M}$ and a grammar symbol $X$, the function $\texttt{goto}(\mathcal{M}, X)$ 
is defined as follows:
$$\texttt{goto}(\mathcal{M}, X) := \texttt{closure}\Bigl( \bigl{ 
   a \rightarrow \beta\, X \bullet \delta:L \bigm| (a \rightarrow \beta \bullet X\, \delta:L) \in \mathcal{M} 
   \bigr} \Bigr).
$$
End of explanation
"""


def all_states(self): 
    start_state  = self.cmp_closure({ ExtendedMarkedRule('ŝ', (), (self.mStart,), frozenset({'$'})) })
    start_state  = combine_rules(start_state)
    self.mStates = { start_state }
    New_States   = self.mStates
    while True:
        More_States = set()
        for Rule_Set in New_States:
            for mr in Rule_Set: 
                if not mr.is_complete():
                    x = mr.symbol_after_dot()
                    next_state = self.goto(Rule_Set, x)
                    if next_state not in self.mStates and next_state not in More_States:
                        More_States.add(next_state)
                        print('.', end='')
        if len(More_States) == 0:
            break
        New_States = More_States;
        self.mStates |= New_States
        print('\n', len(self.mStates), sep='')
    print("All LR-states:")
    counter = 1
    self.mStateNames[start_state] = 's0'
    print(f's0 = {set(start_state)}')
    for state in self.mStates - { start_state }:
        self.mStateNames[state] = f's{counter}'
        print(f's{counter} = {set(state)}')
        counter += 1

Grammar.all_states = all_states
del all_states

"""
Explanation: The function all_states computes the set of all states of an LR-parser.  The function starts with the state
$$ \texttt{closure}\bigl({ \widehat{s} \rightarrow \bullet s : {\$} }\bigr) $$
and then tries to compute new states by using the function goto.  This computation proceeds via a 
fixed-point iteration.  Once all states have been computed, the function assigns names to these states.
This association is stored in the dictionary mStateNames.
End of explanation
"""


def compute_action_table(self):
    self.mActionTable = {}
    print('\nAction Table:')
    for state in self.mStates:
        stateName = self.mStateNames[state]
        actionTable = {}
        # compute shift actions
        for token in self.mTokens:   
            newState  = self.goto(state, token)
            if newState != set():
                newName = self.mStateNames[newState]
                actionTable[token] = ('shift', newName)
                self.mActionTable[stateName, token] = ('shift', newName)
                print(f'action("{stateName}", {token}) = ("shift", {newName})')
        # compute reduce actions
        for mr in state:
            if mr.is_complete():
                for token in mr.mFollow:
                    action1 = actionTable.get(token)
                    action2 = ('reduce', mr.to_rule())
                    if action1 == None:
                        actionTable[token] = action2  
                        r = self.mRuleNames[mr.to_rule()]
                        self.mActionTable[stateName, token] = ('reduce', r)
                        print(f'action("{stateName}", {token}) = {action2}')
                    elif action1 != action2: 
                        self.mConflicts = True
                        print('')
                        print(f'conflict in state {stateName}:')
                        print(f'{stateName} = {state}')
                        print(f'action("{stateName}", {token}) = {action1}')     
                        print(f'action("{stateName}", {token}) = {action2}')
                        print('')
        for mr in state:
            if mr == ExtendedMarkedRule('ŝ', (self.mStart,), (), frozenset({'$'})):
                actionTable['$'] = 'accept'
                self.mActionTable[stateName, '$'] = 'accept'
                print(f'action("{stateName}", $) = accept')

Grammar.compute_action_table = compute_action_table
del compute_action_table

"""
Explanation: The following function computes the action table and is defined as follows:
- If $\mathcal{M}$ contains an extended marked rule of the form $a \rightarrow \beta \bullet t\, \delta:L$
  then we have
  $$\texttt{action}(\mathcal{M},t) := \langle \texttt{shift}, \texttt{goto}(\mathcal{M},t) \rangle.$$
- If $\mathcal{M}$ contains an extended marked rule of the form $a \rightarrow \beta\, \bullet:L$ and we have
  $t \in L$, then we define
  $$\texttt{action}(\mathcal{M},t) := \langle \texttt{reduce}, a \rightarrow \beta \rangle$$
- If $\mathcal{M}$ contains the extended marked rule $\widehat{s} \rightarrow s \bullet:{\$}$, then we define 
  $$\texttt{action}(\mathcal{M},\$) := \texttt{accept}. $$
- Otherwise, we have
  $$\texttt{action}(\mathcal{M},t) := \texttt{error}. $$
End of explanation
"""


def compute_goto_table(self):
    self.mGotoTable = {}
    print('\nGoto Table:')
    for state in self.mStates:
        for var in self.mVariables:
            newState = self.goto(state, var)
            if newState != set():
                stateName = self.mStateNames[state]
                newName   = self.mStateNames[newState]
                self.mGotoTable[stateName, var] = newName
                print(f'goto({stateName}, {var}) = {newName}')

Grammar.compute_goto_table = compute_goto_table
del compute_goto_table

%%time
g = Grammar(grammar)

def strip_quotes(t):
    if t[0] == "'" and t[-1] == "'":
        return t[1:-1]
    return t

def dump_parse_table(self, file):
    with open(file, 'w', encoding="utf-8") as handle:
        handle.write('# Grammar rules:\n')
        for rule in self.mRules:
            rule_name = self.mRuleNames[rule] 
            handle.write(f'{rule_name} =("{rule.mVariable}", {rule.mBody})\n')
        handle.write('\n# Action table:\n')
        handle.write('actionTable = {}\n')
        for s, t in self.mActionTable:
            action = self.mActionTable[s, t]
            t = strip_quotes(t)
            if action[0] == 'reduce':
                rule_name = action[1]
                handle.write(f"actionTable['{s}', '{t}'] = ('reduce', {rule_name})\n")
            elif action == 'accept':
                handle.write(f"actionTable['{s}', '{t}'] = 'accept'\n")
            else:
                handle.write(f"actionTable['{s}', '{t}'] = {action}\n")
        handle.write('\n# Goto table:\n')
        handle.write('gotoTable = {}\n')
        for s, v in self.mGotoTable:
            state = self.mGotoTable[s, v]
            handle.write(f"gotoTable['{s}', '{v}'] = '{state}'\n")
        
Grammar.dump_parse_table = dump_parse_table
del dump_parse_table

g.dump_parse_table('parse-table.py')

!type parse-table.py

!cat parse-table.py

"""
Explanation: The function compute_goto_table computes the goto table.
End of explanation
"""


!del GrammarLexer.* GrammarParser.* Grammar.tokens GrammarListener.py Grammar.interp 
!rmdir /S /Q __pycache__

!dir /B

!rm GrammarLexer.* GrammarParser.* Grammar.tokens GrammarListener.py Grammar.interp 
!rm -r __pycache__

!ls

"""
Explanation: The command below cleans the directory.  If you are running windows, you have to replace rm with del.
End of explanation
"""


