itec.minicompiler
Class Parser

java.lang.Object
  itec.minicompiler.Parser

All Implemented Interfaces:

ConstantsInterface

public class Parser

extends java.lang.Object

implements ConstantsInterface

The Parser implements a top-down-parser for the PL0-language. It uses the FIRST-Sets of the non-terminals and a lookahead Token, which is one step ahead of the actual position, to check for errors. WEAK- and SYNC-points are used for synchronization and a better resumption after errors. To get these WEAK- and SYNC-points the FOLLOW-Sets of the non-terminals are used.

Version:

1.0 (29.09.2004)

Author:

Stefan Leitner, Stefan Schauer

Field Summary

private int	actualColumn The line and column of the actualToken
private int	actualLine The line and column of the actualToken
private Token	actualToken The Token at the actual position of the Parser
private java.util.HashSet	CompareOperators The Sets of compare-operators defined in the grammar
private ErrorHandler	errorhandler The ErrorHandler used by the actual Parser
private FirstSet	firstset The FIRST-Sets of the grammar
private FollowSet	followset The FOLLOW-Sets of the grammar
private java.util.HashSet	LineOperators The Set of line-operators defined in the grammar (+, -, OR)
private int	lookaheadColumn The line and column of the lookaheadToken
private int	lookaheadLine The line and column of the lookaheadToken
private Token	lookaheadToken The Token at the next position of the Parser.
private java.util.HashSet	PointOperators The Set of point-operators defined in the grammar (*, DIV, MOD, &)
private Scanner	scanner The Scanner used by the actual Parser

Fields inherited from interface itec.minicompiler.ConstantsInterface

ACTUALPARAMETERS, AND, ARRAY, ARRAYTYPE, ASSIGNMENT, BECOMES, BEGIN, COLON, COMMA, CONST, DECLARATIONS, DIV, DO, ELSE, ELSIF, EMPTY, END, EPSILON, EQUAL, ERR_EXP_ARRAY, ERR_EXP_BECOMES, ERR_EXP_COLON, ERR_EXP_COMMA, ERR_EXP_DO, ERR_EXP_END, ERR_EXP_EQUAL, ERR_EXP_IDENT, ERR_EXP_IF, ERR_EXP_LPAREN, ERR_EXP_MODULE, ERR_EXP_OF, ERR_EXP_PERIOD, ERR_EXP_PROCEDURE, ERR_EXP_RBRAK, ERR_EXP_RECORD, ERR_EXP_REPEAT, ERR_EXP_RPAREN, ERR_EXP_SEMICOLON, ERR_EXP_THEN, ERR_EXP_UNTIL, ERR_EXP_WHILE, ERR_INV_FACTOR, ERR_INV_STATEMENT, ERR_INV_TYPE, ERR_INVALID_CHARACTER, ERR_NOT_EXP_DECLARATIONS, ERR_NOT_EXP_FACTOR, ERR_NOT_EXP_STATEMENT, ERR_NOT_EXP_TYPE, ERR_NOT_TERMINATED, ERR_NUMBER_TOO_HIGH, EXPRESSION, FACTOR, FIELDLIST, FORMALPARAMETERS, FPSECTION, GEQ, GREATER, IDENT, IDENTLIST, IF, IFSTATEMENT, KEYWORD, LBRAK, LEQ, LESS, LPAREN, MINICOMP, MINUS, MOD, MODULE, NOT, NOTEQUAL, NUMBER, OF, OR, PERIOD, PLUS, PROCEDURE, PROCEDUREBODY, PROCEDURECALL, PROCEDUREDECLARATION, PROCEDUREHEADING, RBRAK, RECORD, RECORDTYPE, REPEAT, REPEATSTATEMENT, RPAREN, SELECTOR, SEMICOLON, SIMPLEEXPRESSION, SINGLE, STATEMENT, STATEMENTSEQUENCE, TERM, THEN, TIMES, TYP, TYPE, UNTIL, VAR, WHILE, WHILESTATEMENT

Constructor Summary

Parser(ErrorHandler e, Scanner s)
Initialize the Parser with an ErrorHandler e and a Scanner s.

Method Summary

private void	actualParameters() Implements the grammar-rule: ActualParameters -> Expression {"," Expression}
private void	arrayType() Implements the grammar-rule: ArrayType -> "ARRAY" Expression "OF" Type
private void	assignment() Implements the grammar-rule: Assignment -> Selector ":=" Expression
private void	declarations() Implements the grammar-rule: Declarations -> ["CONST" {ident "=" Expression} ";"] ["TYPE" {ident "=" Type ";"}] ["VAR" Identlist ":" Type ";"] {ProcedureDeclaration ";"}
private void	error(int n) Call the ErrorHandler with the error number n.
private void	expect(int kind, int nonTerminal) Check wether the next Token is the one which is needed or not.
private void	expectWeak(int kind) Check wether the next Token is the one which is needed or not.
private void	expression() Implements the grammar-rule: Expression -> SimpleExpression [("="|"#"|"<"|"<="|">"|">=") SimpleExpression]
private void	factor() Implements the grammar-rule: Factor -> ((ident Selector)|integer|("("Expression")")|("~" Factor))
private void	fieldList() Implements the grammar-rule: FieldList -> IdentList ":" Type
private void	formalParameters() Implements the grammar-rule: FormalParameters -> FPSection (";" FPSection}
private void	fpSection() Implements the grammar-rule: FPSection -> "VAR" IdentList ":" Type
private void	get() Get the next Token from the Scanner.
private void	identList() Implements the grammar-rule: IdentList -> ident {"," ident}
private void	ifStatement() Implements the grammar-rule: IfStatement -> "IF" Expression "THEN" StatementSequence {"ELSIF" Expression "THEN" StatementSequence} ["ELSE" StatementSequence] "END"
private boolean	isInFirst(int nonTerminal) Return wether the lookaheadToken is in the FIRST-Set of nonTerminal
void	parse() Parse the whole source code
private void	pl0() Implements the grammer-rule: Pl0 -> "MODULE" ident ";" Declarations ["BEGIN" StatementSequence] "END" ident "."
private void	procedureBody() Implements the grammar-rule: ProcedureBody -> Declarations ["BEGIN" StatementSequence] "END"
private void	procedureCall() Implements the grammar-rule: ProcedureCall -> "(" [ActualParameters] ")"
private void	procedureDeclaration() Implements the grammar-rule: ProcedureDeclaration -> ProcedureHeading ";" ProcedureBody ident
private void	procedureHeading() Implements the grammar-rule: ProcedureHeading -> "PROCEDURE" ident "(" [FormalParameters] ")"
private void	recordType() Implements the grammar-rule: RecordType -> "RECORD" FieldList {";" FieldList} "END"
private void	repeatStatement() Implements the grammar-rule: RepeatStaement -> "REPEAT" StatementSequence "UNTIL" Expression
private void	selector() Implements the grammar-rule: Selector -> {("." ident)|("[" Expression "]")}
private void	simpleExpression() Implements the grammar-rule: SimpleExpression -> ["+"|"-"] Term {("+"|"-"|"OR") Term}
private void	statement() Implements the grammar-rule: Statement -> [(ident(Assignment|ProcedureCall)) |IfStatement |WhileStatement |RepeatStatement]
private void	statementSequence() Implements the grammar-rule: StatementSequence -> Statement {";" Statement}
private void	term() Implements the grammar-rule: Term -> Factor {("*"|"DIV"|"MOD"|"&") Factor}
private void	type() Implements the grammar-rule: Type -> (ident|ArrayType|RecordType)
private boolean	weakSeparator(int kind, int nonTerminal) Check wether a seperator (i.e , or ;) is present.
private void	whileStatement() Implements the grammar-rule: WhileStatement -> "WHILE" Expression "DO" StatementSequence "END"

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

firstset

private FirstSet firstset

The FIRST-Sets of the grammar

followset

private FollowSet followset

The FOLLOW-Sets of the grammar

CompareOperators

private java.util.HashSet CompareOperators

The Sets of compare-operators defined in the grammar

LineOperators

private java.util.HashSet LineOperators

The Set of line-operators defined in the grammar (+, -, OR)

PointOperators

private java.util.HashSet PointOperators

The Set of point-operators defined in the grammar (*, DIV, MOD, &)

errorhandler

private ErrorHandler errorhandler

The ErrorHandler used by the actual Parser

scanner

private Scanner scanner

The Scanner used by the actual Parser

actualToken

private Token actualToken

The Token at the actual position of the Parser

lookaheadToken

private Token lookaheadToken

The Token at the next position of the Parser. It is used to make decisions

actualLine

private int actualLine

The line and column of the actualToken

actualColumn

private int actualColumn

The line and column of the actualToken

lookaheadLine

private int lookaheadLine

The line and column of the lookaheadToken

lookaheadColumn

private int lookaheadColumn

The line and column of the lookaheadToken

Constructor Detail

Parser

public Parser(ErrorHandler e,
              Scanner s)

Initialize the Parser with an ErrorHandler e and a Scanner s. Furthermore initialize the FirstSet and FollowSet and the sets of compare-, line- and point-operators.

Parameters:

e - The ErrorHandler the Parser should use

s - The Scanner the Parser gets it's information from

Method Detail

error

private void error(int n)

Call the ErrorHandler with the error number n.

Parameters:

n - The error number of the error which occured

get

private void get()

Get the next Token from the Scanner.

expect

private void expect(int kind,
                    int nonTerminal)

Check wether the next Token is the one which is needed or not. If yes, just read along. Otherwise go to the next SYNC-point using the FOLLOW-Set of the nonTerminal.

Parameters:

kind - The kind of the expected Token

nonTerminal - The non-terminal for which a SYNC-point should be reached

expectWeak

private void expectWeak(int kind)

Check wether the next Token is the one which is needed or not. If yes, just read along. Otherwise throw an error but act like the token was there (i.e. no synchronization has to be done).

Parameters:

kind - The kind of the expected Token

weakSeparator

private boolean weakSeparator(int kind,
                              int nonTerminal)

Check wether a seperator (i.e , or ;) is present. If yes, just read along. Otherwise check if the seperator is really needed or if the statement is finished anyway.

Parameters:

kind - The kind of the expected Token

nonTerminal - The non-terminal

Returns:

True if the seperator is needed or the lookaheadToken is not the expected one, False otherwise

isInFirst

private boolean isInFirst(int nonTerminal)

Return wether the lookaheadToken is in the FIRST-Set of nonTerminal

Parameters:

nonTerminal - The non-terminal for the check

Returns:

True if the lookaheadToken is in the FIRST-Set of nonTerminal, False otherwise

parse

public void parse()

Parse the whole source code

pl0

private void pl0()

Implements the grammer-rule:

Pl0 -> "MODULE" ident ";" Declarations ["BEGIN" StatementSequence] "END" ident "."

declarations

private void declarations()

Implements the grammar-rule:

Declarations -> ["CONST" {ident "=" Expression} ";"] ["TYPE" {ident "=" Type ";"}] ["VAR" Identlist ":" Type ";"] {ProcedureDeclaration ";"}

type

private void type()

Implements the grammar-rule:

Type -> (ident|ArrayType|RecordType)

arrayType

private void arrayType()

Implements the grammar-rule:

ArrayType -> "ARRAY" Expression "OF" Type

recordType

private void recordType()

Implements the grammar-rule:

RecordType -> "RECORD" FieldList {";" FieldList} "END"

fieldList

private void fieldList()

Implements the grammar-rule:

FieldList -> IdentList ":" Type

identList

private void identList()

Implements the grammar-rule:

IdentList -> ident {"," ident}

procedureDeclaration

private void procedureDeclaration()

Implements the grammar-rule:

ProcedureDeclaration -> ProcedureHeading ";" ProcedureBody ident

procedureHeading

private void procedureHeading()

Implements the grammar-rule:

ProcedureHeading -> "PROCEDURE" ident "(" [FormalParameters] ")"

procedureBody

private void procedureBody()

Implements the grammar-rule:

ProcedureBody -> Declarations ["BEGIN" StatementSequence] "END"

formalParameters

private void formalParameters()

Implements the grammar-rule:

FormalParameters -> FPSection (";" FPSection}

fpSection

private void fpSection()

Implements the grammar-rule:

FPSection -> "VAR" IdentList ":" Type

statementSequence

private void statementSequence()

Implements the grammar-rule:

StatementSequence -> Statement {";" Statement}

statement

private void statement()

Implements the grammar-rule:

Statement -> [(ident(Assignment|ProcedureCall)) |IfStatement |WhileStatement |RepeatStatement]

assignment

private void assignment()

Implements the grammar-rule:

Assignment -> Selector ":=" Expression

selector

private void selector()

Implements the grammar-rule:

Selector -> {("." ident)|("[" Expression "]")}

procedureCall

private void procedureCall()

Implements the grammar-rule:

ProcedureCall -> "(" [ActualParameters] ")"

actualParameters

private void actualParameters()

Implements the grammar-rule:

ActualParameters -> Expression {"," Expression}

ifStatement

private void ifStatement()

Implements the grammar-rule:

IfStatement -> "IF" Expression "THEN" StatementSequence {"ELSIF" Expression "THEN" StatementSequence} ["ELSE" StatementSequence] "END"

whileStatement

private void whileStatement()

Implements the grammar-rule:

WhileStatement -> "WHILE" Expression "DO" StatementSequence "END"

repeatStatement

private void repeatStatement()

Implements the grammar-rule:

RepeatStaement -> "REPEAT" StatementSequence "UNTIL" Expression

expression

private void expression()

Implements the grammar-rule:

Expression -> SimpleExpression [("="|"#"|"<"|"<="|">"|">=") SimpleExpression]

simpleExpression

private void simpleExpression()

Implements the grammar-rule:

SimpleExpression -> ["+"|"-"] Term {("+"|"-"|"OR") Term}

term

private void term()

Implements the grammar-rule:

Term -> Factor {("*"|"DIV"|"MOD"|"&") Factor}

factor

private void factor()

Implements the grammar-rule:

Factor -> ((ident Selector)|integer|("("Expression")")|("~" Factor))