Re: CFG for L(G) and L(G')

"jason_box" <cppisfun@xxxxxxxxx> writes:

Given a CFG G where epsilon is in L(G), how would you create a new
grammar L(G' = L(G) - epsilon? I know there is a method that allows you
to change a grammar G where epsilon is not part of L(G) and you can get
a equivalent grammar G' having no epsilon production. The question
arises when you have epislon as part of the lanaguage. Thank you for
help in adanced.

If a production has more than two symbols on the RHS, add new
productions to reduce the number. For example, rewrite

N -> ABCD

to

N -> AN'
N' -> BN"
N" -> CD

Then calculate for each nonterminal if it is nullable.

If you have a production N -> AB, where A and B are terminals or
nonterminals, add new productions according to the following rules:

1. If A is a nullable nonterminal, add N -> B
2. If B is a nullable nonterminal, add N -> A

Now remove all empty productions.

Torben
.

Relevant Pages

  • Single production vs recursive grammar structure
    ... The InstanceOfExpressionproduction and the other ones directly ... void InstanceOfExpression(): ... RelationalExpression() [... ... grammar, ...
    (comp.compilers.tools.javacc)
  • Re: C# 2.0 language grammar
    ... While I agree that it probably boiled down to an arbitrary decision, ... namespace-type-name production is used is in the context of a using-directive ... particular productions are used, and according to the grammar it is, then I ... question the logic in constructing the namespace-name and namespace-type-name ...
    (microsoft.public.dotnet.languages.csharp)
  • "Z -> z versus Z -> z e" - sole thread for future discussion/postings
    ... When WE suggesting replacing the production rule Z -> z e ... with the rule Z -> e to terminate the derivation, ... Suppose a grammar G ... of a linear grammar that introduce a non-terminal, ...
    (comp.theory)
  • "Z -> z versus Z -> z e" - sole thread for future discussion/postings
    ... When WE suggesting replacing the production rule Z -> z e ... with the rule Z -> e to terminate the derivation, ... Suppose a grammar G ... of a linear grammar that introduce a non-terminal, ...
    (sci.math)
  • "Z -> z versus Z -> z e" - sole thread for future discussion/postings
    ... When WE suggesting replacing the production rule Z -> z e ... with the rule Z -> e to terminate the derivation, ... Suppose a grammar G ... of a linear grammar that introduce a non-terminal, ...
    (sci.logic)