=?gb2312?q?=BB=D8=B8=B4=A3=BA=20Re:=20[antlr-interest]=20parser=20nondete?= =?gb2312?q?rminism=20rule?=

[=?gb2312?q?=CB=EF=BC=CD=B8=D5=20Jigang=20(Robert)=20Sun?=]

My parser rules-- 
 
graphExp: (brackGraph)+ (options {greedy=true;}:op graphExp)*;

op        : funcName;// contains constructorName;  UpperCaseId | LowerCaseId | FunnyId;
brackGraph: graphVar | ("(" graphExp ")")=> "(" graphExp ")" | constructor | specialExp;
specialExp: basicValue;
graphVar  : var;//var is Varible in Clean language report
constructor: constructorName | "("! constructorName ")"!;

is based on Clean Language report at
ftp://ftp.cs.kun.nl/pub/Clean/Clean20/doc/CleanRep2.0.pdf

relevant grammar from the report is (on page 113,116 ,117)

GraphExpr = Application //I merged this rule with the next, so Application is not used
Application = {BrackGraph}+ | GraphExpr Operator GraphExpr//I did left recursion elimination at
this
Operator = FunctionName | ConstructorName

BrackGraph = GraphVariable
  | Constructor
  | Function
  | (GraphExpr)
  | LambdaAbstr
  | CaseExpr
  | LetExpr
  | SpecialExpression
  | DynamicExpression

Constructor = onstructorName | (ConstructorName)

FunctionName = LowerCaseId | UpperCaseId | FunnyId
ConstructorName = UpperCaseId | FunnyId
Variable = LowerCaseId

//the following is terminals
LowerCaseId; = LowerCaseChar~{IdChar}
UpperCaseId = UpperCaseChar~{IdChar}
FunnyId = {SpecialChar}+

My parser rules is a subset of it. I wish you can check if I have done the left recurion
elimination  properly. It must be my cause, there should be no problem with the Clean language
specification. 

Thanks.

Jigang 

--- Bans VGLab <bans.vglab at gmail.com>дµÀ:

> Hello Jigang,
> 
> The first rule can be re-written like this:
> 
> graphExp
>     : brackGraph
>         (
>             brackGraph
>             |
>         )+
>         (options {greedy=true;}:op graphExp)*
>     ;
> 
> So, the statement "between alt 1 and exit branch of block" means the first
> alternative in the grammar expression " brackGraph |  " and its exit.
> 
> This can be easily seen with this example derivation:
> 
> Applying different alternatives in the rule 1, we can derive
> 
> "brackGraph op graphExp"
>           and
> "brackGraph brackGraph brackGraph".
> 
> But both of them will eventually derive
>    "op op op"
> 
> So looking at the next terminal LA(1) which could be any of the "UpperCaseId
> | LowerCaseId | FunnyId", there is no way to predict which alternative to
> pick. This can go to arbitrary depth. So, increasing k to any value will not
> solve the problem. You need to re-structure the grammar.
> 
> Hope this helps.
> 
> -Sujeet Banerjee
> SMTS
> Persistent Systems Pvt. Ltd.
> 
> On 7/19/06, Ëï¼Í¸Õ Jigang (Robert) Sun <sunjigang1965 at yahoo.com.cn> wrote:
> >
> > I have a parser rule,
> >
> > graphExp: (brackGraph)+ (options {greedy=true;}:op graphExp)*;  //line 101
> >
> > brackGraph: op | ("(" graphExp ")")=> "(" graphExp ")"
> >
> > op: UpperCaseId | LowerCaseId | FunnyId;
> >
> > I know op (UpperCaseId | LowerCaseId | FunnyId) is either part of
> > brackGraph or (op graphExp)*,
> > and in (op graphExp)*  op could be a subset of graphExp,
> >
> > so warning was given:
> >
> > par.g:101: warning:nondeterminism upon
> > par.g:101:     k==1:UpperCaseId,LowerCaseId,FunnyId
> > par.g:101:     between alt 1 and exit branch of block
> >
> > I have not got an idea about it.
> >
> > Thanks.
> >
> > Jigang
> >
> >
> >
> >
> > ___________________________________________________________
> > ÑÅ»¢Ãâ·ÑÓÊÏä-3.5GÈÝÁ¿£¬20M¸½¼þ
> > http://cn.mail.yahoo.com/
> >
> 



		
___________________________________________________________ 
ÇÀ×¢ÑÅ»¢Ãâ·ÑÓÊÏä-3.5GÈÝÁ¿£¬20M¸½¼þ£¡ 
http://cn.mail.yahoo.com