<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Implementing an SLR-Table-Generator
A Grammar for Grammars
As the goal is to generate an SLR-table-generator we first need to implement a parser for context free grammars.
The file simple.g contains an example grammar that describes arithmetic expressions.
Step1:  We use <span style="font-variant
Step2:  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,) + 𝛽.
Step3:  We start by generating both scanner and parser.
Step4:  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__.
Step5:  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.
Step6:  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 "'".
Step7:  Fun Fact
Step8:  Given a list Rules of GrammarRules, the function collect_variables(Rules) returns the set of all variables occuring in Rules.
Step9:  Given a set Rules of GrammarRules, the function collect_tokens(Rules) returns the set of all tokens and literals occuring in Rules.
Step10:  Marked Rules
The class MarkedRule stores a single marked rule of the form
$$ v \rightarrow \alpha \bullet \beta $$
where the variable $v$ is stored in the member variable mVariable, while $\alpha$ and $\beta$ are stored in the variables mAlphaand mBeta respectively.  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__.
Step11:  Given a marked rule self, the function is_complete checks, whether the marked rule self has the form
$$ c \rightarrow \alpha\; \bullet,$$
i.e. it checks, whether the $\bullet$ is at the end of the grammar rule.
Step12:  Given a marked rule self of the form
$$ c \rightarrow \alpha \bullet X\, \delta, $$
the function symbol_after_dot returns the symbol $X$. If there is no symbol after the $\bullet$, the method returns None.
Step13:  Given a marked rule, this function returns the variable following the dot.  If there is no variable following the dot, the function returns None.
Step14:  The function move_dot(self) transforms a marked rule  of the form 
$$ c \rightarrow \alpha \bullet X\, \beta $$
into a marked rule of the form
$$ c \rightarrow \alpha\, X \bullet \beta, $$
i.e. the $\bullet$ is moved over the next symbol.  Invocation of this method assumes that there is a symbol
following the $\bullet$.
Step15:  The function to_rule(self) turns the marked rule self into  a GrammarRule, i.e. the marked rule
$$ c \rightarrow \alpha \bullet \beta $$
is turned into the grammar rule
$$ c \rightarrow \alpha\, \beta. $$
Step16:  SLR-Table-Generation
The class Grammar represents a context free grammar.  It stores a list of the GrammarRules of the given grammar.
Each grammar rule is of the form
$$ a \rightarrow \beta $$
where $\beta$ is a tuple of variables, tokens, and literals.
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 SLR-parser.  These states are sets of 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.
Step17:  Given a set of Variables, the function initialize_dictionary returns a dictionary that assigns the empty set to all variables.
Step18:  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 SLR-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.
Step19:  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.
Step20:  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$
Step21:  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{''}$.
Step22:  The arguments S and T of eps_union are sets that contain tokens and, additionally, they might contain the empty string.
Step23:  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
Step24:  If $\mathcal{M}$ is a set of marked rules, then the closure of $\mathcal{M}$ is the smallest set $\mathcal{K}$ such that
we have the following
Step25:  Given a set of marked rules $\mathcal{M}$ and a grammar symbol $X$, the function $\texttt{goto}(\mathcal{M}, X)$ 
is defined as follows
Step26:  The function all_states computes the set of all states of an SLR-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.
Step27:  The following function computes the action table and is defined as follows
Step28:  The function compute_goto_table computes the goto table.
<ASSISTANT_TASK:>
Python Code:
!cat Examples/c-grammar.g
Explanation: Implementing an SLR-Table-Generator
A Grammar for Grammars
As the goal is to generate an SLR-table-generator we first need to implement a parser for context free grammars.
The file simple.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
"'return'".islower()
Explanation: Fun Fact: The invocation of "'return'".islower() returns True.  This is the reason that we have to test that
name does not start with a "'" character because otherwise keywords like 'return' or 'while' appearing in a grammar would be mistaken for variables.
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 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.__repr__())
    
    def __repr__(self):
        alphaStr = ' '.join(self.mAlpha)
        betaStr  = ' '.join(self.mBeta)
        return f'{self.mVariable} → {alphaStr} • {betaStr}'
Explanation: Marked Rules
The class MarkedRule stores a single marked rule of the form
$$ v \rightarrow \alpha \bullet \beta $$
where the variable $v$ is stored in the member variable mVariable, while $\alpha$ and $\beta$ are stored in the variables mAlphaand mBeta respectively.  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
MarkedRule.is_complete = is_complete
del is_complete
Explanation: Given a marked rule self, the function is_complete checks, whether the marked rule self has the form
$$ c \rightarrow \alpha\; \bullet,$$
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
MarkedRule.symbol_after_dot = symbol_after_dot
del symbol_after_dot
Explanation: Given a marked rule self of the form
$$ c \rightarrow \alpha \bullet X\, \delta, $$
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 next_var(self):
    if len(self.mBeta) > 0:
        var = self.mBeta[0]
        if is_var(var):
            return var
    return None
MarkedRule.next_var = next_var
del next_var
Explanation: Given a 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 MarkedRule(self.mVariable, 
                      self.mAlpha + (self.mBeta[0],), 
                      self.mBeta[1:])
MarkedRule.move_dot = move_dot
del move_dot
Explanation: The function move_dot(self) transforms a marked rule  of the form 
$$ c \rightarrow \alpha \bullet X\, \beta $$
into a marked rule of the form
$$ c \rightarrow \alpha\, X \bullet \beta, $$
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)
MarkedRule.to_rule = to_rule
del to_rule
Explanation: The function to_rule(self) turns the marked rule self into  a GrammarRule, i.e. the marked rule
$$ c \rightarrow \alpha \bullet \beta $$
is turned into the grammar rule
$$ c \rightarrow \alpha\, \beta. $$
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: SLR-Table-Generation
The class Grammar represents a context free grammar.  It stores a list of the GrammarRules of the given grammar.
Each grammar rule is of the form
$$ a \rightarrow \beta $$
where $\beta$ is a tuple of variables, tokens, and literals.
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 SLR-parser.  These states are sets of 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 SLR-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
            for rule in self.mRules:
                head, alpha = rule.mVariable, rule.mBody
                if c == head:
                    More_Rules |= { MarkedRule(head, (), alpha) }
        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 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$ is a marked rule from 
  $\mathcal{K}$, and $c$ is a variable and if, furthermore,
  $c \rightarrow \gamma$ is a grammar rule,
  then the marked rule $c \rightarrow \bullet \gamma$
  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) \in \mathcal{K}
  $$
We define $\texttt{closure}(\mathcal{M}) := \mathcal{K}$.  The function cmp_closure computes this closure for a given set of 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 self.cmp_closure(Result)
Grammar.goto = goto
del goto
Explanation: Given a set of 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 \bigm| (a \rightarrow \beta \bullet X\, \delta) \in \mathcal{M} 
   \bigr} \Bigr).
$$
End of explanation
def all_states(self): 
    start_state  = self.cmp_closure({ MarkedRule('ŝ', (), (self.mStart, '$')) })
    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()
                    if x != '$':
                        More_States |= { self.goto(Rule_Set, x) }
        if More_States <= self.mStates:
            break
        New_States = More_States - self.mStates;
        self.mStates |= New_States
    print("All SLR-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 SLR-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:
            if token != '$':
                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 self.mFollow[mr.mVariable]:
                    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 == MarkedRule('ŝ', (self.mStart,), ('$',)):
                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 a marked rule of the form $a \rightarrow \beta \bullet t\, \delta$
  then we have
  $$\texttt{action}(\mathcal{M},t) := \langle \texttt{shift}, \texttt{goto}(\mathcal{M},t) \rangle.$$
- If $\mathcal{M}$ contains a marked rule of the form $a \rightarrow \beta\, \bullet$ and we have
  $t \in \texttt{Follow}(a)$, then we define
  $$\texttt{action}(\mathcal{M},t) := \langle \texttt{reduce}, a \rightarrow \beta \rangle$$
- If $\mathcal{M}$ contains the 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') 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')
!cat parse-table.py
!rm GrammarLexer.* GrammarParser.* Grammar.tokens GrammarListener.py Grammar.interp 
!rm -r __pycache__
!ls
Explanation: The function compute_goto_table computes the goto table.
End of explanation
<END_TASK>