|Calculating maximum number of grammar productions email@example.com (2006-05-15)|
|Re: Calculating maximum number of grammar productions firstname.lastname@example.org (Oliver Wong) (2006-06-03)|
|Date:||15 May 2006 22:24:10 -0400|
|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?
Return to the
Search the comp.compilers archives again.