CocoR/Sample grammars/Other Formats/m2pim3_LL1.g

/* ANTLR v3 Grammar for Modula-2 (PIM3)
 *
 * LL(1) version, derived from 3rd Edition of Programming in Modula-2
 *
 * This grammar is a refactored  LL(1) version of the Modula-2 syntax provided
 * in appendix 1 of  "Programming in Modula-2", Third, Corrected Edition 1985,
 * by  Niklaus  Wirth,  Springer  Verlag,  ISBN 0-387-15078-1.  It follows the
 * naming conventions and structure of Wirth's grammar but has been refactored
 * to satisfy LL(1) constraints.  The original, unmodified grammar by Wirth is
 * also available in ANTLR v3 format as a separate file.
 *
 *
 * Copyright (C) 2009, Benjamin Kowarsch. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * (1) Hosting of  this  file, or any parts thereof, on websites which contain
 *     advertising is expressly forbidden and requires specific prior written
 *     permission. However, the ANTLR project website and university websites
 *     are exempt from this restriction. Exemption may be withdrawn if abused.
 *
 * (2) Redistributions of source code must retain the above copyright notice,
 *     this list of conditions and the following disclaimer.
 *
 * (3) Redistributions in binary form must reproduce the above copyright
 *     notice, this list of conditions and the following disclaimer in the
 *     documentation and other materials provided with the distribution.
 *
 * (4) Neither the author's name nor the names of any contributors may be used
 *     to endorse or promote products derived from this software without
 *     specific prior written permission.
 *
 * (5) Where this list of conditions or the following disclaimer, in part or
 *     as a whole is overruled or nullified by applicable law, no permission
 *     is granted to use the software.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING,  BUT NOT LIMITED TO,  THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY  AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT  SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
 * LIABLE  FOR  ANY  DIRECT,  INDIRECT,  INCIDENTAL,  SPECIAL,  EXEMPLARY,  OR
 * CONSEQUENTIAL  DAMAGES  (INCLUDING,  BUT  NOT  LIMITED  TO,  PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES;  LOSS OF USE,  DATA,  OR PROFITS; OR BUSINESS
 * INTERRUPTION)  HOWEVER  CAUSED  AND ON ANY THEORY OF LIABILITY,  WHETHER IN
 * CONTRACT,  STRICT LIABILITY,  OR TORT  (INCLUDING NEGLIGENCE  OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,  EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 *
 */

grammar m2pim3_LL1; // Modula-2 PIM3 standard

// file version 1.01, June 22, 2009

options {
  backtrack = false;
  k=1;  /* LL(1) */
}

tokens { // Reserved Words
	AND            = 'AND';
	ARRAY          = 'ARRAY';
	BEGIN          = 'BEGIN';
	BY             = 'BY';
	CASE           = 'CASE';
	CONST          = 'CONST';
	DEFINITION     = 'DEFINITION';
	DIV            = 'DIV';
	DO             = 'DO';
	ELSE           = 'ELSE';
	ELSIF          = 'ELSIF';
	END            = 'END';
	EXIT           = 'EXIT';
	EXPORT         = 'EXPORT';
	FOR            = 'FOR';
	FROM           = 'FROM';
	IF             = 'IF';
	IMPLEMENTATION = 'IMPLEMENTATION';
	IMPORT         = 'IMPORT';
	IN             = 'IN';
	LOOP           = 'LOOP';
	MOD            = 'MOD';
	MODULE         = 'MODULE';
	NOT            = 'NOT';
	OF             = 'OF';
	OR             = 'OR';
	POINTER        = 'POINTER';
	PROCEDURE      = 'PROCEDURE';
	QUALIFIED      = 'QUALIFIED';
	RECORD         = 'RECORD';
	REPEAT         = 'REPEAT';
	RETURN         = 'RETURN';
	SET            = 'SET';
	THEN           = 'THEN';
	TO             = 'TO';
	TYPE           = 'TYPE';
	UNTIL          = 'UNTIL';
	VAR            = 'VAR';
	WHILE          = 'WHILE';
	WITH           = 'WITH';
}

// ---------------------------------------------------------------------------
// P A R S E R   G R A M M A R
// ---------------------------------------------------------------------------

// ***** PIM 3 Appendix 1 line 1 *****

ident :	IDENT ; // see lexer

// ***** PIM 3 Appendix 1 line 2 *****

number : INTEGER | REAL ; // see lexer

// ***** PIM 3 Appendix 1 lines 3-4 *****

integer : INTEGER ; // see lexer

// ***** PIM 3 Appendix 1 line 5 *****

real : REAL ; // see lexer

// ***** PIM 3 Appendix 1 line 6 *****

scaleFactor : SCALE_FACTOR ; // see lexer

// ***** PIM 3 Appendix 1 line 7 *****

hexDigit : HEX_DIGIT ; // see lexer

// ***** PIM 3 Appendix 1 line 8 *****

digit : DIGIT ; // see lexer

// ***** PIM 3 Appendix 1 line 9 *****

octalDigit : OCTAL_DIGIT ; // see lexer

// ***** PIM 3 Appendix 1 line 10 *****

string : STRING ; // see lexer

// ***** PIM 3 Appendix 1 line 11 *****

qualident :
	ident ( '.' ident )*
	;

// ***** PIM 3 Appendix 1 line 12 *****

constantDeclaration :	
	ident '=' constExpression
	;

// ***** PIM 3 Appendix 1 line 13 *****

constExpression :
	expression
	;

//  ***** PIM 3 Appendix 1 line 14 *****

typeDeclaration :
	ident '=' type
	;

//  ***** PIM 3 Appendix 1 lines 15-16 *****

type :
	simpleType | arrayType | recordType | setType | pointerType | procedureType
	;

// ***** PIM 3 Appendix 1 line 17 *****

// refactored for LL(1)
simpleType :
	subrangeTypeOrQualident |
	enumeration
	;

// new for for LL(1)
subrangeTypeOrQualident :
	range |
	qualident /* <= factored out */ range?
	;

// new for LL1(1)
range :
	'[' constExpression '..' constExpression ']'
	;

// ***** PIM 3 Appendix 1 line 18 *****

enumeration :
	'(' identList ')'
	;

// ***** PIM 3 Appendix 1 line 19 *****

identList :
	ident ( ',' ident )*
	;

// ***** PIM 3 Appendix 1 line 20 *****

// replaced for LL(1), see subrangeTypeOrQualident

// ***** PIM 3 Appendix 1 line 21 *****

arrayType :
	ARRAY simpleType ( ',' simpleType )* OF type
	;

// ***** PIM 3 Appendix 1 line 22 *****

recordType :
	RECORD fieldListSequence END
	;

// ***** PIM 3 Appendix 1 line 23 *****

fieldListSequence :
	fieldList ( ';' fieldList )*
	;

// ***** PIM 3 Appendix 1 lines 24-26 *****

fieldList :
	( identList ':' type |
	  CASE ident? ':' qualident OF variant ( '|' variant )*
	  ( ELSE fieldListSequence )?
	END )?
	;

// ***** PIM 3 Appendix 1 line 27 *****

variant :
	( caseLabelList ':' fieldListSequence )?
	;

// ***** PIM 3 Appendix 1 line 28 *****

caseLabelList :
	caseLabels ( ',' caseLabels )*
	;

// ***** PIM 3 Appendix 1 line 29 *****

caseLabels :
	constExpression ( '..' constExpression )?
	;

// ***** PIM 3 Appendix 1 line 30 *****

setType :
	SET OF simpleType
	;

// ***** PIM 3 Appendix 1 line 31 *****

pointerType :
	POINTER TO type
	;

// ***** PIM 3 Appendix 1 line 32 *****

procedureType :
	PROCEDURE formalTypeList?
	;

// ***** PIM 3 Appendix 1 lines 33 *****

formalTypeList :
	'(' ( VAR? formalType ( ',' VAR? formalType )* )? ')'
	( ':' qualident )?
	;

// ***** PIM 3 Appendix 1 line 35 *****

variableDeclaration :
	identList ':' type
	;

// ***** PIM 3 Appendix 1 line 36 *****

// refactored for LL(1)
designator :
	qualident ( designatorTail )?
	;

// new for LL(1)
designatorTail :
	( ( '[' expList ']' | '^' ) ( '.' ident )* )+
	;

// new for LL(1)
setOrDesignator :
	qualident /* <= factored out */
	( set | designatorTail )?
	;

// ***** PIM 3 Appendix 1 line 37 *****

expList :
	expression ( ',' expression )*
	;

// ***** PIM 3 Appendix 1 line 38 *****

expression :
	simpleExpression ( relation simpleExpression )?
	;

// ***** PIM 3 Appendix 1 line 39 *****

relation :
	'=' | '#' | '<' | '<=' | '>' | '>=' | 'IN'
	{} /* make ANTLRworks display separate branches */
	;

// ***** PIM 3 Appendix 1 line 40 *****

simpleExpression :
	( '+' | '-' {})? term ( addOperator term )*
	;

// ***** PIM 3 Appendix 1 line 41 *****

addOperator :
	'+' | '-' | 'OR'
	{} /* make ANTLRworks display separate branches */
	;

// ***** PIM 3 Appendix 1 line 42

term :
	factor ( mulOperator factor )*
	;

// ***** PIM 3 Appendix 1 line 43 *****

// Note: PIM3 text says '&' is a synonym for 'AND'
//       but the grammar does not actually show it
mulOperator :
	'*' | '/' | DIV | MOD | AND | '&'
	{} /* make ANTLRworks display separate branches */
	;

// ***** PIM 3 Appendix 1 lines 44-45 *****

// refactored for LL(1)
//
// Note: PIM3 text says '~' is a synonym for 'NOT'
//       but the grammar does not actually show it
factor :
	number |
	string |
	set |
	qualident ( set | designatorTail? actualParameters? ) |
	'(' expression ')' | ( NOT | '~' {}) factor
	;

// ***** PIM 3 Appendix 1 line 46 *****

// refactored for LL(1)
set :
	/* qualident has been factored out */
	'{' ( element ( ',' element )* )? '}'
	;

// ***** PIM 3 Appendix 1 line 47 *****

element :
	expression ( '..' expression )?
	;

// ***** PIM 3 Appendix 1 line 48 *****

actualParameters :
	'(' expList? ')'
	;

// ***** PIM 3 Appendix 1 lines 49-52 *****

// refactored for LL(1)
statement :
	( assignmentOrProcCall | ifStatement | caseStatement |
	  whileStatement | repeatStatement | loopStatement |
	  forStatement | withStatement | EXIT | RETURN expression? )?
	;

// ***** PIM 3 Appendix 1 line 53 *****

// and

// ***** PIM 3 Appendix 1 line 54 *****

// both replaced by

// new for LL(1)
assignmentOrProcCall :
	designator /* has been factored out */
	( ':=' expression | actualParameters? )
	;

// ***** PIM 3 Appendix 1 line 55 *****

statementSequence :
	statement ( ';' statement )*
	;

// ***** PIM 3 Appendix 1 lines 56-58 *****

ifStatement :
	IF expression THEN statementSequence
	( ELSIF expression THEN statementSequence )*
	( ELSE statementSequence )?
	END
	;

// ***** PIM 3 Appendix 1 lines 59-60 *****

caseStatement :
	CASE expression OF case ( '|' case )*
	( ELSE statementSequence )?
	END
	;

// ***** PIM 3 Appendix 1 line 61 *****

case :
	( caseLabelList ':' statementSequence )?
	;

// ***** PIM 3 Appendix 1 line 62 *****

whileStatement :
	WHILE expression DO statementSequence END
	;

// ***** PIM 3 Appendix 1 line 63 *****

repeatStatement :
	REPEAT statementSequence UNTIL expression
	;

// ***** PIM 3 Appendix 1 lines 64-65 *****

forStatement :
	FOR ident ':=' expression TO expression ( BY constExpression )?
	DO statementSequence END
	;

// ***** PIM 3 Appendix 1 line 66 *****

loopStatement :
	LOOP statementSequence END
	;

// ***** PIM 3 Appendix 1 line 67 *****

withStatement :
	WITH designator DO statementSequence END
	;

// ***** PIM 3 Appendix 1 line 68 *****

procedureDeclaration :
	procedureHeading ';' block ident
	;

// ***** PIM 3 Appendix 1 line 69 *****

procedureHeading :
	PROCEDURE ident formalParameters?
	;

// ***** PIM 3 Appendix 1 line 70 *****

block :
	declaration*
	( BEGIN statementSequence )? END
	;

// ***** PIM 3 Appendix 1 lines 71-74 *****

declaration :
	CONST ( constantDeclaration ';' )* |
	TYPE ( typeDeclaration ';' )* |
	VAR ( variableDeclaration ';' )* |
	procedureDeclaration ';' |
	moduleDeclaration ';'
	;

// ***** PIM 3 Appendix 1 lines 75-76 *****

formalParameters :
	'(' ( fpSection ( ';' fpSection )* )? ')' ( ':' qualident )?
	;

// ***** PIM 3 Appendix 1 line 77 *****

fpSection :
	VAR? identList ':' formalType
	;

// ***** PIM 3 Appendix 1 line 78 *****

formalType :
	( ARRAY OF )? qualident
	;

// ***** PIM 3 Appendix 1 lines 79-80 *****

moduleDeclaration :
	MODULE ident priority? ';'
	importList* exportList?
	block ident
	;

// ***** PIM 3 Appendix 1 line 81 *****

priority :
	'[' constExpression ']'
	;

// ***** PIM 3 Appendix 1 line 82 *****

// Note, ANTLR treats 'export' as a reserved word
//       => rule name changed to 'exportList'
exportList :
	EXPORT QUALIFIED? identList ';'
	;

// ***** PIM 3 Appendix 1 line 83 *****

// Note, ANTLR treats 'import' as a reserved word
//       => rule name changed to 'importList'
importList :
	( FROM ident )? IMPORT identList ';'
	;

// ***** PIM 3 Appendix 1 lines 84-85 *****

definitionModule :
	DEFINITION MODULE ident ';'
	importList*
	definition*
	END ident '.'
	;

// ***** PIM 3 Appendix 1 lines 86-89 *****

definition :
	CONST ( constantDeclaration ';' )* |
	TYPE ( ident ( '=' type )? ';' )* |
	VAR ( variableDeclaration ';' )* |
	procedureHeading ';'
	;

// ***** PIM 3 Appendix 1 line 90 *****

programModule :
	MODULE ident priority? ';'
	importList* block ident '.'
	;

// ***** PIM 3 Appendix 1 lines 91 *****

compilationUnit :	
	definitionModule | IMPLEMENTATION? programModule
	;

// ---------------------------------------------------------------------------
// L E X E R   G R A M M A R
// ---------------------------------------------------------------------------

// ***** PIM 3 Appendix 1 line 1 *****

IDENT :	LETTER ( LETTER | DIGIT )* ;

// ***** PIM 3 Appendix 1 lines 3-4 *****

INTEGER :
	DIGIT+ |
	OCTAL_DIGIT+ ( 'B' | 'C' {}) |
	DIGIT HEX_DIGIT* 'H'
	;

// ***** PIM 3 Appendix 1 line 5 *****

REAL :
	DIGIT+ '.' DIGIT* SCALE_FACTOR?
	;

// ***** PIM 3 Appendix 1 line 6 *****

fragment
SCALE_FACTOR :
	'E' ( '+' | '-' {})? DIGIT+
	;

// ***** PIM 3 Appendix 1 line 7 *****

fragment
HEX_DIGIT :
	DIGIT | 'A' | 'B' | 'C' | 'D' | 'E' | 'F'
	{} /* make ANTLRworks display separate branches */
	;

// ***** PIM 3 Appendix 1 line 8 *****

fragment
DIGIT :
	OCTAL_DIGIT | '8' | '9'
	{} /* make ANTLRworks display separate branches */
	;

// ***** PIM 3 Appendix 1 line 9 *****

fragment
OCTAL_DIGIT :
	'0' | '1' | '2' | '3' | '4' | '5' | '6' | '7'
	{} /* make ANTLRworks display separate branches */
	;

// ***** PIM 3 Appendix 1 line 10 *****

// Nore, the formal definition of string in PIM3 does not match
//       the plain English description of string in the text.
//       => changed to match textual description
STRING :
	'\'' ( CHARACTER | '"' )* '\'' | '"' ( CHARACTER | '\'' )* '"'
	;

// ***** PIM3 provides no formal definition for letter *****

fragment
LETTER : 'A' .. 'Z' | 'a' .. 'z' ;

// ***** PIM3 provides no formal definition for character *****

fragment
CHARACTER :
	// any printable characters other than single and double quote
	' ' | '!' | '#' | '$' | '%' | '&' | '(' | ')' | '*' | '+' |
	',' | '-' | '.' | ':' | ';' | '<' | '=' | '>' | '?' | '@' |
	'[' | '\\' | ']' | '^' | '_' | '`' | '{' | '|' | '}' | '~' |
	DIGIT | LETTER
	;

// ***** PIM3 provides no formal definition for comment *****

COMMENT :	
	'(*' ( options { greedy = false; } : . )* COMMENT '*)'
	{ channel = hidden; }
	;

// ***** PIM3 provides no formal definition for whitespace *****

WHITESPACE :
	( ' ' | '\t' | '\u000C' | '\r' | '\n')
	{ channel = hidden; }
	;

// END OF FILE