15 May 2006 22:24:10 -0400

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

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

Return to the
comp.compilers page.

Search the
comp.compilers archives again.