1324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#!/usr/bin/ruby 2324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# encoding: utf-8 3324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 4324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverrequire 'antlr3/test/functional' 5324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 6324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverclass TestLLStarParser < ANTLR3::Test::Functional 7324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver inline_grammar( <<-'END' ) 8324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver grammar LLStar; 9324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 10324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver options { language = Ruby; } 11324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver @header { require 'stringio' } 12324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver @init { @output = StringIO.new() } 13324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver @members { 14324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def output 15324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver @output.string 16324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver end 17324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 18324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 19324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver program 20324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver : declaration+ 21324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ; 22324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 23324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** In this rule, the functionHeader left prefix on the last two 24324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * alternatives is not LL(k) for a fixed k. However, it is 25324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * LL(*). The LL(*) algorithm simply scans ahead until it sees 26324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * either the ';' or the '{' of the block and then it picks 27324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * the appropriate alternative. Lookhead can be arbitrarily 28324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * long in theory, but is <=10 in most cases. Works great. 29324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Use ANTLRWorks to see the look use (step by Location) 30324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * and look for blue tokens in the input window pane. :) 31324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 32324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver declaration 33324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver : variable 34324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver | functionHeader ';' 35324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { @output.puts( $functionHeader.name + " is a declaration") } 36324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver | functionHeader block 37324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { @output.puts( $functionHeader.name + " is a definition") } 38324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ; 39324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 40324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver variable 41324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver : type declarator ';' 42324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ; 43324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 44324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver declarator 45324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver : ID 46324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ; 47324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 48324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver functionHeader returns [name] 49324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver : type ID '(' ( formalParameter ( ',' formalParameter )* )? ')' 50324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver {$name = $ID.text} 51324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ; 52324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 53324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver formalParameter 54324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver : type declarator 55324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ; 56324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 57324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver type 58324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver : 'int' 59324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver | 'char' 60324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver | 'void' 61324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver | ID 62324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ; 63324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 64324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver block 65324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver : '{' 66324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver variable* 67324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver stat* 68324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver '}' 69324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ; 70324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 71324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver stat: forStat 72324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver | expr ';' 73324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver | block 74324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver | assignStat ';' 75324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver | ';' 76324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ; 77324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 78324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver forStat 79324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver : 'for' '(' assignStat ';' expr ';' assignStat ')' block 80324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ; 81324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 82324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver assignStat 83324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver : ID '=' expr 84324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ; 85324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 86324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver expr: condExpr 87324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ; 88324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 89324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver condExpr 90324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver : aexpr ( ('==' | '<') aexpr )? 91324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ; 92324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 93324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver aexpr 94324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver : atom ( '+' atom )* 95324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ; 96324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 97324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver atom 98324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver : ID 99324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver | INT 100324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver | '(' expr ')' 101324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ; 102324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 103324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ID : ('a'..'z'|'A'..'Z'|'_') ('a'..'z'|'A'..'Z'|'0'..'9'|'_')* 104324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ; 105324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 106324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver INT : ('0'..'9')+ 107324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ; 108324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 109324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver WS : ( ' ' 110324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver | '\t' 111324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver | '\r' 112324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver | '\n' 113324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver )+ 114324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver {$channel=HIDDEN} 115324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ; 116324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver END 117324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 118324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 119324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver example "parsing with a LL(*) grammar" do 120324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver lexer = LLStar::Lexer.new( <<-'END'.fixed_indent( 0 ) ) 121324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver char c; 122324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int x; 123324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 124324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void bar(int x); 125324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 126324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int foo(int y, char d) { 127324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int i; 128324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (i=0; i<3; i=i+1) { 129324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver x=3; 130324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver y=5; 131324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 132324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 133324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver END 134324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver parser = LLStar::Parser.new lexer 135324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 136324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver parser.program 137324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver parser.output.should == <<-'END'.fixed_indent( 0 ) 138324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bar is a declaration 139324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver foo is a definition 140324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver END 141324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver end 142324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 143324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverend 144