Re: Calculating maximum number of grammar productions

<ali@hodroj.net> wrote in message news:06-05-051@comp.compilers...
> Hello,
>
> Given a LALR grammar and a set of language tokens. Is there an
> algorithm to find out how many productions are possible for a specific
> token-wide length statement. For example:
>
> Consider the following grammar:
>
> Expr:
> Expr + Expr | Expr - Expr | 1 | 0
>
> for example: a 5 token-wide length production would be one that has 5
> tokens in it,
> like: 1 + 1 - 0
>
> For a simple grammar like above, you can come up with a mathematical
> formula using factorials or permutations to calculate how many possible
> productions you can have, However, what if you have language like C ?
> assuming--to make things simple-- for every token type there is only
> one associated string (ie: a variable name is always "var", a function
> name is always "function"), what would be a suitable algorithm to
> calculate the possible number of productions for a specific number of
> tokens in a statement?


        It might help to first convert the grammar to chomsky normal form (see
http://en.wikipedia.org/wiki/Chomsky_normal_form)


<quote>
Every grammar in Chomsky normal form is context-free, and conversely, every
context-free grammar can be efficiently transformed into an equivalent one
which is in Chomsky normal form.
[...]
throughout the derivation of a string, each string of terminals and
nonterminals is always either the same length or one element longer than the
previous such string. The derivation of a string of length n is always
exactly 2n-1 steps long. Furthermore, since all rules deriving nonterminals
transform one nonterminal to exactly two nonterminals, a parse tree based on
a grammar in Chomsky normal form is a binary tree, and the height of this
tree is limited to at most the length of the string.
</quote>


So basically, you walk the grammar tree, counting all possible derivations,
always stopping when you reach height n, because you know if you go to a
deeper height, you will end up with a string exceeding length n.


        - Oliver

Return to the comp.compilers page.
Search the comp.compilers archives again.