Calculating maximum number of grammar productions
15 May 2006 22:24:10 -0400

          From comp.compilers

Related articles
Calculating maximum number of grammar productions (2006-05-15)
Re: Calculating maximum number of grammar productions (Oliver Wong) (2006-06-03)
| List of all articles for this month |

Newsgroups: comp.compilers
Date: 15 May 2006 22:24:10 -0400
Keywords: question, theory
Posted-Date: 15 May 2006 22:24:10 EDT


        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 | 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?


Post a followup to this message

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