# Calculating maximum number of grammar productions

## ali@hodroj.net15 May 2006 22:24:10 -0400

From comp.compilers

Related articles
Calculating maximum number of grammar productions ali@hodroj.net (2006-05-15)
Re: Calculating maximum number of grammar productions owong@castortech.com (Oliver Wong) (2006-06-03)
| List of all articles for this month |

 From: ali@hodroj.net Newsgroups: comp.compilers Date: 15 May 2006 22:24:10 -0400 Organization: http://groups.google.com Keywords: question, theory Posted-Date: 15 May 2006 22:24:10 EDT

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?

Thanks!

Post a followup to this message