Search code examples
grammarlexical

lexical elements of grammar

There is 4 lexical elements of grammar

G = (S, N, T, P)

Where G = Grammar, S = Start Symbol, N = Non-Terminals, T = Terminals, P = Production rules

I wanted to know if N is always equal with P because as I know P are lexemes which may replace with other lexemes

So in this example:

<program> --> <stmts>
<stmts> --> <stmt> | <stmt> ; <stmts>
<stmt> --> <var> = <expr>
<var> --> a | b | c | d
<expr> --> <term> + <term> | <term> - <term>
<term> --> <var> | const

S: <program>
N: <program>, <stmts>, <var>, <expr>, <term>
T: ;, a, b, c, d, +, -, const
P: <program>, <stmts>, <var>, <expr>, <term>

Is that right?

Solution

  • No. |N| does not necessarily = |P|. Consider:

    <program> --> <stmts>
<stmts> --> <stmt> 
<stmts> -->| <stmt> ; <stmts>
<stmt> --> <var> = <expr>
<var> --> a 
<var> --> b
<var> --> c
<var> --> d
<expr> --> <term> + <term> 
<expr> --> <term> - <term>
<term> --> <var> 
<term> --> const

    Your problem is that you are not precise about what is allowed in a grammar rule.

    You can force the number of rules to match nonterminals, by insisting that no rule has the same left hand side. To do that, you can't insist on simple BNF; you have to have extended BNF with at least alternation.

    PS: This isn't really about "lexical elements" of a grammar. It is just about the definition of a grammar.