CFG Reader(First)

A. Fifth Edition
This is fifth?fourth? edition of my CFG Reader which stands for Context-Free-Grammar Reader. In this edition, 
I finished the first set calculation and add a meta symbol---"{", "}".
B.The problem
What is First set?
Example: A  -> a | b c | V
The variable A will have a first set of First(A) = {a, b, First(V)}.

program -> stmt-sequence
stmt-sequence -> stmt-sequence ; statement | statement
statement -> if-stmt | repeat-stmt | assign-stmt | read-stmt | write-stmt
if-stmt -> if boolean-exp then stmt-sequence end
| if boolean-exp then stmt-sequence else stmt-sequence end
repeat-stmt -> repeat stmt-sequence until boolean-exp
assign-stmt -> identifier := integer-exp
read-stmt -> read identifier
write-stmt -> write integer-exp
boolean-exp -> integer-exp comparison-op integer-exp
comparison-op -> < | =
integer-exp -> integer-exp addop term | term
addop -> + | -
term -> term mulop factor | factor
mulop -> * | /
factor -> ( integer-exp ) | number | identifier

 

C.The idea of program
 
This problem has a standard algorithm in text. So, will you just refer to the text if you are really interested in?
I highly suspect if there is anyone in my reader group would be interested in reading this or even want to have 
any idea of "what is First" and how to calculate. 
D.The major functions
E.Further improvement
F.File listing
1. CFGReader.h
2. CFGReader.cpp  
3. Grammar.h
4. Grammar.cpp
5. main.cpp (main)
 
 
file name: CFGReader.h
#include "Grammar.h"


class CFGReader
{
private:
	char buffer[BufferLength];
	FILE* stream;
	void newRule(const char* str);
	void readRule();
	void addRule(const char* str);
	int addToken(const char* str, bool isTerminal=true);
	void printRule(int index);
public:
	void readFromFile(const char* fileName);
	void optimize();
	void print();
};



file name: CFGReader.cpp 
#include <iostream>
#include "CFGReader.h"

using namespace std;

Grammar grammar;

const char* deliStr=" |\n";

//this would only remove the immediate left recursion
//and should I expand it to remove all kinds of left-recursion?


void CFGReader::readFromFile(const char* fileName)
{
	if ((stream=fopen(fileName, "r"))==NULL)
	{
		cout<<"cannot open file "<<fileName<<endl;
	}
	else
	{		
		readRule();		
	}
}

void CFGReader::readRule()
{
	char* ptr=buffer;
	char* hold;
	int count=0;

	while (!feof(stream))
	{
		count=0;
		fgets(buffer, BufferLength-1, stream);
		ptr=buffer;	
		
		while ((ptr=strtok(ptr, " \n"))!=NULL)
		{
			if (strcmp(ptr, "|")!=0)
			{
				//test the first two token to see if old rule continues
				if (count==0)				
				{
					hold=ptr;
				}
				if (count==1)
				{
					if (strcmp("->", ptr)==0)
					{			
						/*
						curIndex=addToken(hold, false);//the index of cur token	
						grammar[curIndex]->terminal=false;
						newRule();	
						*/
						newRule(hold);
					}
					else
					{								
						addRule(hold);
						addRule(ptr);															
					}
				}
				if (count>=2)//always add
				{
					addRule(ptr);
				}
				count++;
			}
			else
			{
				//this is an alternative production rule
				newRule(NULL);						
			}
			ptr=NULL;
		}		
	}
}

void CFGReader::newRule(const char* str)
{
	grammar.newRule(str);
}

void CFGReader::optimize()
{
	grammar.optimize();
}


void CFGReader::addRule(const char* str)
{
	grammar.addRule(str);
}

int CFGReader::addToken(const char* str, bool isTerminal)
{
	return grammar.addToken(str, isTerminal);
}



void CFGReader::printRule(int index)
{
	grammar.printRule(index);
}

void CFGReader::print()
{
	grammar.print();
	grammar.printToken();
}




  
file name: Grammar.h
const int BufferLength=256;
const int MaxTokenCount=80;
const int MaxRHSCount=50;
const int MaxRuleCount=200;
const int MaxTokenLength=10;
const int MaxProduction=10;

struct Token
{
	bool isMeta;
	bool terminal;
	bool isNull;
	char* name;
	int production[MaxProduction];//pointer to the production it gives
	int count;
	int firstCount;
	int followCount;
	int follow[MaxTokenCount];
	int first[MaxTokenCount];
};

class Grammar
{
private:
	Token* token[MaxTokenCount];
	int tokenCount;
	int curIndex;//the index of current token
	int curPos;//the position at production rule
	//MaxRuleCount>=MaxVariableCount!!!
	int production[MaxRuleCount][MaxRHSCount];
	int prodIndex;//pointing to current production, initialized to -1
	int checkRecursion(int tIndex, int curToken);
	bool addIntoFirst(int target, int source);
	bool addFirst(int target, int source);
	void shiftRule(int ruleIndex, bool Left2Right, int offset);
	void addAtEnd(int ruleIndex, int toAdd);
	void addRuleForToken(int tIndex, int ruleIndex);
	int copyRule(int source, int target);//return the position of -1
	void replaceRule(int curToken, int ruleIndex);
	void initialize();
	void removeRuleFromToken(int tIndex, int ruleIndex);
	void checkEpsilon(int ruleIndex);
	void removeImmediate(int tIndex, int ruleIndex);
	void doAddRule(int tIndex);
	void commonLeftFactor();
	int findCommonFactor(int tokenIndex, int ruleIndex);
	void removeLeftRecursion();
	void doCommonFactor(int tokenIndex, int ruleIndex, int index);
	int forgeToken(int index);//create a new variable
	void epsilonRule(int ruleIndex);
	//void calculateNull();
	void calculateFirst();
	void calculateFollow();
	void calculateNull();
	bool Null(int tIndex);
	bool addFirstTerminal(int target, int source);
	bool addFirstNonTerminal(int target, int source);
	void calculateProperty();
public:
	Grammar();
	void optimize();
	void printRule(int index);
	void print();
	void printToken();
	void addRule(const char* str);
	void newRule(const char* str);//this is an internal method, not suitable for outside
	Token* operator[](int index);
	int addToken(const char* str, bool isTerminal=true);
	Token* createToken(const char* theName, bool isTerminal);
	int tokenIndex(const char* str);
};
 
file name: Grammar.cpp 
#include <iostream>
#include "Grammar.h"

using namespace std;

const char* emptyStr="e";
const char* optionBegin="{";
const char* optionEnd="}";
int emptyIndex=-1;

void Grammar::calculateProperty()
{
	calculateNull();
	calculateFirst();
	calculateFollow();
}

void Grammar::printToken()
{
	for (int i=0; i<tokenCount; i++)
	{
		cout<<"name: "<<token[i]->name<<endl;
		cout<<"   isNull: "<<(token[i]->isNull?"true":"false")<<endl;
		cout<<"   isTerminal: "<<(token[i]->terminal?"true":"false")<<endl;
		cout<<"   first: ";
		for (int j=0; j<token[i]->firstCount; j++)
		{
			if (j!=0)
			{
				cout<<",";
			}
			cout<<"["<<j<<"]="<<token[token[i]->first[j]]->name;			
		}
		cout<<endl;
	}
}

//must use while loop to discover new set!!!!!
void Grammar::calculateFirst()
{
	int i;
	bool addNew;
	do
	{
		i=0;
		addNew=false;
		while (i<tokenCount)
		{		
			//the terminal contains itself
			if (token[i]->terminal)
			{
				//addFirst don't judge if it is nullable!!
				addFirst(i, i);			
				//token[i]->first[token[i]->firstCount++]=i;
			}
			else
			{
				//for all its rules
				for (int j=0; j<token[i]->count; j++)
				{
					int theToken, k=0;
					theToken=production[token[i]->production[j]][k];
					//for each token in each rule
					do 
					{
						//add non epsilon set
						if (addIntoFirst(i, theToken))
						{
							addNew=true;
						}
						//if it is not null, means it is end
						if (!token[theToken]->isNull)
						{
							break;
						}
						//if it is nullable, continue
						k++;
						theToken=production[token[i]->production[j]][k];
					}while (theToken!=-1);
					//it means all token in this rule is nullable, so
					if (theToken==-1)
					{
						//it is nullable
						//addEpsilonIntoFirst(i);
						addFirst(i, emptyIndex);
					}
				}
			}
			i++;
		}		
	}while (addNew);
}

void Grammar::calculateFollow()
{
}

void Grammar::addRuleForToken(int tIndex, int ruleIndex)
{
	token[tIndex]->production[token[tIndex]->count++]=ruleIndex;
}

void Grammar::shiftRule(int ruleIndex, bool left2Right, int offset)
{
	int end=0;
	while (production[ruleIndex][end]!=-1)
	{
		end++;
	}
	if (left2Right)
	{
		for (int i=end; i>=0; i--)
		{
			production[ruleIndex][i+offset]=production[ruleIndex][i];
		}
	}
	else
	{
		for (int i=0; i<=end-offset; i++)
		{
			production[ruleIndex][i]=production[ruleIndex][i+offset];
		}
		checkEpsilon(ruleIndex);
	}
}

void Grammar::checkEpsilon(int ruleIndex)
{
	if (production[ruleIndex][0]==-1)
	{
		epsilonRule(ruleIndex);
	}
}

bool Grammar::addFirstTerminal(int target, int source)
{
	//addFirst
	token[target]->first[token[target]->firstCount++]=source;
	//if it is epsilon
	if (token[source]->isNull)
	{
		//token[target]->isNull=true;//unless all is
		return true;
	}
	return false;
}

bool Grammar::addFirst(int target, int source)
{
	//don't calculate meta symbol
	if (token[source]->isMeta)
	{
		return false;
	}
	//check if it is already there
	for (int i=0; i<token[target]->firstCount; i++)
	{
		if (token[target]->first[i]==source)
		{
			return false;
		}
	}
	//add at end
	token[target]->first[token[target]->firstCount++]=source;
	return true;
}

//add non epsilon into it.
bool Grammar::addIntoFirst(int target, int source)
{
	bool addNew=false;
	for (int i=0; i<token[source]->firstCount; i++)
	{
		//add non epsilon
		if (!token[token[source]->first[i]]->isNull)
		{
			if (addFirst(target, token[source]->first[i]))
			{
				addNew=true;
			}
		}
	}
	return addNew;
}
	/*
	int theToken;
	bool added, tokenIsNull=false;
	//if the token epsilon is added, surely the token will be nullable
	if (token[source]->terminal)
	{
		return addFirstTerminal(int target, int source));			
	}
	else
	{
		added=false;
		for (int i=0; i<token[source]->count; i++)
		{
			int j=0;
			theToken=production[token[source]->production[i]][j];
			do
			{
				if (token[theToken]->terminal)
				{
					//it means it is terminal epsilon
					if (!addFirstTerminal(target, theToken))
					{
						break;
					}
				}
				else
				{
					//if it is nullable
					if (!addFirstNonTerminal(target, theToken))
					{
						break;
					}
				}
				j++;
				theToken=production[token[source]->production[i]][j];
			}while (theToken!=-1);
			//it must be the case that every choice is nullable
			if (theToken==-1)
			{
				token[target]->isNull=true;
			}					
		}
	}

	return true;
	*/


bool Grammar::Null(int tIndex)
{
	if (token[tIndex]->terminal)
	{
		return token[tIndex]->isNull;		
	}
	for (int i=0; i<token[tIndex]->count; i++)
	{
		int j=0, theToken;
		theToken=production[token[tIndex]->production[i]][j];
		do
		{
			if (!Null(theToken))
			{
				break;
			}
			j++;
			theToken=production[token[tIndex]->production[i]][j];
		}while (theToken!=-1);
		if (theToken==-1)
		{			
			return true;
		}
	}
	return false;
}

void Grammar::calculateNull()
{
	for (int i=0; i<tokenCount; i++)
	{
		token[i]->isNull=Null(i);	
	}
}
		

void Grammar::addAtEnd(int ruleIndex, int toAdd)
{
	int end=0;
	while (production[ruleIndex][end]!=-1)
	{
		end++;
	}
	production[ruleIndex][end++]=toAdd;
	production[ruleIndex][end]=-1;
}

//left-recursion:  A -> A a | b | c
//change to: A  -> b A' | c A'
//			 A' -> a A' | empty
void Grammar::removeImmediate(int tIndex, int ruleIndex)
{
	int newIndex=forgeToken(tIndex);
	int holdRuleIndex=token[tIndex]->production[ruleIndex];
	//sequence matters!

	//change to: A -> b A'
	for (int i=0; i<token[tIndex]->count; i++)
	{
		if (i!=ruleIndex)
		{
			addAtEnd(token[tIndex]->production[i], newIndex);
		}
	}
	
	//shift
	/*
	token[tIndex]->count--;
	for (i=ruleIndex; i<token[tIndex]->count; i++)
	{
		token[tIndex]->production[i]=token[tIndex]->production[i+1];
	}
	*/
	removeRuleFromToken(tIndex, ruleIndex);
	
	addRuleForToken(newIndex, holdRuleIndex);
	//token[newIndex]->production[token[newIndex]->count++]=holdRuleIndex;

	shiftRule(holdRuleIndex, false, 1);
	addAtEnd(holdRuleIndex, newIndex);
	
	//add epsilon rule for new variable
	epsilonRule(++prodIndex);
	addRuleForToken(newIndex, prodIndex);
}


int Grammar::forgeToken(int index)
{
	char str[MaxTokenLength+2], ch;
	int len=strlen(token[index]->name);
	int temp=0, i=0;
	strcpy(str, token[index]->name);
	ch=str[len-1];//get last char of name
	if (ch>='0'&&ch<'9')
	{
		str[len-1]=ch+i+1;
	}
	else
	{
		str[len]='0'+i;
		str[len+1]='\0';
	}
	//I won't bother to check repetitation of name
	while (tokenIndex(str)!=-1)
	{
		i++;
		if (ch>='0'&&ch<'9')
		{
			str[len-1]=ch+i+1;
		}
		else
		{
			str[len]='0'+i;
			str[len+1]='\0';
		}
	}

	return addToken(str, false);//it is non-terminal for sure	
}

int Grammar::copyRule(int source, int target)
{
	int i=0;
	while (production[source][i]!=-1) 
	{
		production[target][i]=production[source][i];
		i++;
	}
	production[target][i]=-1;
	return i;
}

void Grammar::doAddRule(int tIndex)
{	
	token[tIndex]->production[token[tIndex]->count++]=++prodIndex;
}

void Grammar::addRule(const char* str)
{
	int index;
	index=addToken(str);
	production[prodIndex][curPos++]=index;
	production[prodIndex][curPos]=-1;//set end
}


//if the token is already there, it return the index
//otherwise, it add new node in token array
int Grammar::addToken(const char* str, bool isTerminal)
{
	int index;
	index=tokenIndex(str);
	if (index==-1)
	{
		index=tokenCount;
	}
	else
	{		
		return index;
	}
	token[index]=createToken(str, isTerminal);	
	tokenCount++;
	if (strcmp(str, emptyStr)==0)
	{
		token[index]->isNull=true;
		emptyIndex=index;
	}
	return index;
}

void Grammar::newRule(const char* str)
{
	if (str!=NULL)
	{
		curIndex=addToken(str, false);
	}
	//add one pointer
	token[curIndex]->production[token[curIndex]->count++]=++prodIndex;
	token[curIndex]->terminal=false;
	curPos=0;//reset to restart;
}

Token* Grammar::createToken(const char* theName, bool isTerminal)
{
	Token* ptr=new Token;
	ptr->name=new char[strlen(theName)+1];
	strcpy(ptr->name, theName);
	ptr->terminal=isTerminal;
	ptr->count=ptr->firstCount=ptr->followCount=0;
	ptr->isNull=false;
	if (strcmp(theName, optionBegin)==0||strcmp(theName, optionEnd)==0)
	{
		ptr->isMeta=true;
	}
	else
	{
		ptr->isMeta=false;
	}
	return ptr;
}

int Grammar::tokenIndex(const char* str)
{
	for (int i=0; i<tokenCount; i++)
	{
		if (strcmp(str, token[i]->name)==0)
		{
			return i;
		}
	}
	return -1;
}

int Grammar::checkRecursion(int tIndex, int curToken)
{
	for (int i=0; i<token[curToken]->count; i++)
	{
		//token[tIndex]->production[i]=ruleIndex
		//production[ruleIndex][0] is the first left-recursion one
		if (production[token[curToken]->production[i]][0]<=curToken)
		{
			return i;
		}
	}
	return -1;
}

void Grammar::printRule(int index)
{
	int nodeIndex=0;
	while (production[index][nodeIndex]!=-1)
	{
		cout<<token[production[index][nodeIndex]]->name<<" ";
		nodeIndex++;
	}
}



void Grammar::initialize()
{
	tokenCount=curIndex=curPos=0;
	prodIndex=-1;//in order to ++ blindly
}

Grammar::Grammar()
{
	initialize();
}

void Grammar::removeLeftRecursion()
{
	int tIndex=0, curToken=0;
	bool newChange=false;
	while (tIndex<tokenCount)
	{		
		if (!token[tIndex]->terminal)
		{
			for (int i=0; i<token[tIndex]->count; i++)
			{
				curToken=production[token[tIndex]->production[i]][0];
				if (curToken<=tIndex&&!token[curToken]->terminal)
				{
					if (curToken!=tIndex)
					{
						replaceRule(tIndex, i);
					}
					else
					{
						removeImmediate(tIndex, i);
					}
					newChange=true;				
				}
			}
		}
		//whenever there is some new findings, restart
		if (!newChange)
		{
			tIndex++;
		}
		else
		{
			tIndex=0;
			newChange=false;
		}
	}
}

void Grammar::replaceRule(int tIndex, int ruleIndex)
{
	int pos, j, targetEnd, sourceEnd, curRule;
	int curToken=production[token[tIndex]->production[ruleIndex]][0];
	for (int i=token[curToken]->count-1; i>=0; i--)
	{
		if (i>0)
		{
			doAddRule(tIndex);
			pos=copyRule(token[curToken]->production[i], prodIndex);
			j=0;
			while (production[token[tIndex]->production[ruleIndex]][j+1]!=-1)
			{
				production[prodIndex][pos+j]=
					production[token[tIndex]->production[ruleIndex]][j+1];
				j++;
			}
			production[prodIndex][pos+j]=-1;
		}
		else
		{
			targetEnd=sourceEnd=0;
			curRule=token[tIndex]->production[ruleIndex];
			while (true)
			{
				if (production[token[curToken]->production[0]][sourceEnd]==-1&&
				production[curRule][targetEnd]==-1)
				{
					break;
				}
				if (production[token[curToken]->production[0]][sourceEnd]!=-1)
				{
					sourceEnd++;
				}
				if (production[curRule][targetEnd]!=-1)
				{
					targetEnd++;
				}
			}
			j=targetEnd+sourceEnd-1;
			while (j>=0)
			{
				if (j>=sourceEnd)
				{
					production[curRule][j]=production[curRule][j-sourceEnd+1];
				}
				else
				{
					production[curRule][j]=production[token[curToken]->production[0]][j];
				}
				j--;
			}
		}
	}
}


//optimize sequence is first common-factor then remove left recursion
//therefore I don't have to check if for same variable if there will be
//more than one left-recursion
void Grammar::optimize()
{
	removeLeftRecursion();
	commonLeftFactor();
	calculateNull();
	calculateFirst();
	calculateFollow();
}

int Grammar::findCommonFactor(int tIndex, int ruleIndex)
{
	for (int i=ruleIndex+1; i<token[tIndex]->count; i++)
	{	
		//if the two rule has the same first token
		if (production[token[tIndex]->production[ruleIndex]][0]==
			production[token[tIndex]->production[i]][0])
		{
			/*
			//calculate if there is epsilon
			if (emptyIndex==-1)
			{
				emptyIndex=tokenIndex(emptyStr);
			}
			//if it is not epsilon
			if (production[token[tIndex]->production[i]][0]!=emptyIndex)
			{
				return i;
			}
			*/
			return i;
		}
	}
	return -1;
}

void Grammar::epsilonRule(int ruleIndex)
{
	production[ruleIndex][0]=addToken(emptyStr);
	production[ruleIndex][1]=-1;
}

//sample:  x -> Aa 
//         x -> Ab
//changed to:  x -> Ax' //this is to change the old rule
//             x' -> b //this is to change the old rule
//             x' -> a //this is the new-added rule
void Grammar::doCommonFactor(int tIndex, int ruleIndex, int index)
{
	int newTokenIndex=forgeToken(tIndex);//create a new variable
	//move the second and after part to the new rule of new variable
	//doing: x' -> a
	//curPos=0;
	//prepare to add one new rule 	
	addRuleForToken(newTokenIndex, ++prodIndex);
	//token[newTokenIndex]->production[token[newTokenIndex]->count++]=++prodIndex;
	token[newTokenIndex]->terminal=false;

	copyRule(token[tIndex]->production[ruleIndex], prodIndex);
	shiftRule(prodIndex, false, 1);
	/*
	do
	{
		
		//do copying
		production[prodIndex][curPos]=
			production[token[tIndex]->production[ruleIndex]][curPos+1];
		curPos++;
	//even the -1 at end is copied
	}while (production[token[tIndex]->production[ruleIndex]][curPos]!=-1);
	*/

	//in order to show an empty string, in case the string is "epsilon"

	
	/*
	if (curPos==1)
	{
		epsilonRule(prodIndex);
	}
	*/


	//replace x -> Aa with x -> Ax'
	production[token[tIndex]->production[ruleIndex]][1]=newTokenIndex;
	production[token[tIndex]->production[ruleIndex]][2]=-1;//end
	
	//doing: x' -> b
	//curPos=0;
	//prepare to add one new rule 
	//pointing new token to where old rule lies
	addRuleForToken(newTokenIndex, token[tIndex]->production[index]);
	/*
	token[newTokenIndex]->production[token[newTokenIndex]->count++]=
		token[tIndex]->production[index];
		*/

	shiftRule(token[tIndex]->production[index], false, 1);
	/*
	do 
	{
		//left-shift productions
		production[token[tIndex]->production[index]][curPos]=
			production[token[tIndex]->production[index]][curPos+1];
		curPos++;

	}while (production[token[tIndex]->production[index]][curPos]!=-1);
	*/
	//add epsilon
	/*
	if (curPos==1)
	{
		epsilonRule(token[tIndex]->production[index]);
	}
	*/
	//remove from token's production array the rule-index----"index"
	//shrink the array by one
	/*
	for (int i=index; i<token[tIndex]->count; i++)
	{
		token[tIndex]->production[i]=token[tIndex]->production[i+1];
	}
	token[tIndex]->count--;
	*/
	removeRuleFromToken(tIndex, index);
}

void Grammar::removeRuleFromToken(int tIndex, int ruleIndex)
{
	for (int i=ruleIndex; i<token[tIndex]->count; i++)
	{
		token[tIndex]->production[i]=token[tIndex]->production[i+1];
	}
	token[tIndex]->count--;
}


void Grammar::commonLeftFactor()
{
	int index=-1, tIndex=0, ruleIndex=0;
	bool flag;
	//whenever a newrule is done, restart!
	while (tIndex<tokenCount)
	{
		ruleIndex=0;
		flag=false;		
		while (ruleIndex<token[tIndex]->count)
		{			
			index=findCommonFactor(tIndex, ruleIndex);
			if (index!=-1)
			{
				doCommonFactor(tIndex, ruleIndex, index);
				//restart
				flag=true;
				break;
			}
			else
			{
				ruleIndex++;
			}
		}
		if (flag)
		{
			tIndex=0;		
		}
		else
		{
			tIndex++;
		}
	}
}

Token* Grammar::operator[](int index)
{
	if (index>=0&&index<tokenCount)
	{
		return token[index];
	}
	else
	{
		return NULL;
	}
}

void Grammar::print()
{
	for (int i=0; i<tokenCount; i++)
	{		
		if (!token[i]->terminal)
		{
			cout<<token[i]->name<<" ==> ";
			for (int j=0; j<token[i]->count; j++)
			{			
				printRule(token[i]->production[j]);	
				if (j!=token[i]->count-1)
				{
					cout<<" | ";
				}
			}
			cout<<"\n";
		}		
	}
}


file name: main.cpp (main)
#include <iostream>
#include "CFGReader.h"

using namespace std;

int main()
{
	CFGReader R;
	R.readFromFile("c:\\ruleTest.txt");
    R.optimize();
	R.print();
	return 0;
}
 
 
The input is something like following:
Please note that all tokens must be separated by space, including "|" and "->" and "{", "}" is meta symbol 
equivalent to Kaleen star. The file is here.
M' -> program i ; Dl B
Dl -> Dv Ml
Ml -> Ml M | e
M -> module i ( Vl ) Dv B
Dv -> variables Vl | e
Vl -> Vl V | V
v -> Il : T ;
T -> integer Ad ; | char Ad
Il -> i | Il , i
Ad -> e | array [ n ]
B -> begin Sl end ;
Sl -> S | S Sl
S -> L := E ; | if C then S else S | loop Sl end ; | exit ; i ( Lp ) ; | B | read Ln ; | write Ln ; | e ;
Lp -> e | Ln
Ln -> L { , L }
L -> i Ar
Ar -> e | [ E ]
E -> F { Oa F }
Oa -> + | -
F -> R { Om R }
Om -> * | /
R -> L | n | ( E ) | c
C -> E Or E
Or -> = | < | > | <= | >=





Here is the result:
M' ==> program i ; Dl B
Dl ==> Dv Ml
B ==> begin Sl end ;
Dv ==> variables Vl  | e
Ml ==> e Ml0
M ==> module i ( Vl ) Dv B
Vl ==> V Vl0
v ==> Il : T ;
Il ==> i Il0
T ==> integer Ad ;  | char Ad
Ad ==> e  | array [ n ]
Sl ==> S Sl0
S ==> L := E ;  | if C then S else S  | loop Sl end ;  | exit ; i ( Lp ) ;  | begin Sl end ;  | read
 Ln ;  | write Ln ;  | e ;
L ==> i Ar
E ==> F { Oa F }
C ==> F { Oa F } Or E
Lp ==> e  | Ln
Ln ==> i Ar { , L }
Ar ==> e  | [ E ]
F ==> R { Om R }
Oa ==> +  | -
R ==> i Ar  | n  | ( E )  | c
Om ==> *  | /
Or ==> =  | <  | >  | <=  | >=
Ml0 ==> module i ( Vl ) Dv B Ml0  | e
Vl0 ==> V Vl0  | e
Il0 ==> , i Il0  | e
Sl0 ==> e  | Sl
name: M'
   isNull: false
   isTerminal: false
   first: [0]=program
name: program
   isNull: false
   isTerminal: true
   first: [0]=program
name: i
   isNull: false
   isTerminal: true
   first: [0]=i
name: ;
   isNull: false
   isTerminal: true
   first: [0]=;
name: Dl
   isNull: true
   isTerminal: false
   first: [0]=e,[1]=variables,[2]=module
name: B
   isNull: false
   isTerminal: false
   first: [0]=begin
name: Dv
   isNull: true
   isTerminal: false
   first: [0]=e,[1]=variables
name: Ml
   isNull: true
   isTerminal: false
   first: [0]=e,[1]=module
name: M
   isNull: false
   isTerminal: false
   first: [0]=module
name: e
   isNull: true
   isTerminal: true
   first: [0]=e
name: module
   isNull: false
   isTerminal: true
   first: [0]=module
name: (
   isNull: false
   isTerminal: true
   first: [0]=(
name: Vl
   isNull: false
   isTerminal: false
   first: [0]=V
name: )
   isNull: false
   isTerminal: true
   first: [0]=)
name: variables
   isNull: false
   isTerminal: true
   first: [0]=variables
name: V
   isNull: false
   isTerminal: true
   first: [0]=V
name: v
   isNull: false
   isTerminal: false
   first: [0]=i
name: Il
   isNull: false
   isTerminal: false
   first: [0]=i
name: :
   isNull: false
   isTerminal: true
   first: [0]=:
name: T
   isNull: false
   isTerminal: false
   first: [0]=integer,[1]=char
name: integer
   isNull: false
   isTerminal: true
   first: [0]=integer
name: Ad
   isNull: true
   isTerminal: false
   first: [0]=e,[1]=array
name: char
   isNull: false
   isTerminal: true
   first: [0]=char
name: ,
   isNull: false
   isTerminal: true
   first: [0]=,
name: array
   isNull: false
   isTerminal: true
   first: [0]=array
name: [
   isNull: false
   isTerminal: true
   first: [0]=[
name: n
   isNull: false
   isTerminal: true
   first: [0]=n
name: ]
   isNull: false
   isTerminal: true
   first: [0]=]
name: begin
   isNull: false
   isTerminal: true
   first: [0]=begin
name: Sl
   isNull: false
   isTerminal: false
   first: [0]=begin,[1]=;,[2]=i,[3]=if,[4]=loop,[5]=exit,[6]=read,[7]=write
name: end
   isNull: false
   isTerminal: true
   first: [0]=end
name: S
   isNull: false
   isTerminal: false
   first: [0]=begin,[1]=;,[2]=i,[3]=if,[4]=loop,[5]=exit,[6]=read,[7]=write
name: L
   isNull: false
   isTerminal: false
   first: [0]=i
name: :=
   isNull: false
   isTerminal: true
   first: [0]=:=
name: E
   isNull: false
   isTerminal: false
   first: [0]=i,[1]=n,[2]=(,[3]=c
name: if
   isNull: false
   isTerminal: true
   first: [0]=if
name: C
   isNull: false
   isTerminal: false
   first: [0]=i,[1]=n,[2]=(,[3]=c
name: then
   isNull: false
   isTerminal: true
   first: [0]=then
name: else
   isNull: false
   isTerminal: true
   first: [0]=else
name: loop
   isNull: false
   isTerminal: true
   first: [0]=loop
name: exit
   isNull: false
   isTerminal: true
   first: [0]=exit
name: Lp
   isNull: true
   isTerminal: false
   first: [0]=e,[1]=i
name: read
   isNull: false
   isTerminal: true
   first: [0]=read
name: Ln
   isNull: false
   isTerminal: false
   first: [0]=i
name: write
   isNull: false
   isTerminal: true
   first: [0]=write
name: {
   isNull: false
   isTerminal: true
   first:
name: }
   isNull: false
   isTerminal: true
   first:
name: Ar
   isNull: true
   isTerminal: false
   first: [0]=e,[1]=[
name: F
   isNull: false
   isTerminal: false
   first: [0]=i,[1]=n,[2]=(,[3]=c
name: Oa
   isNull: false
   isTerminal: false
   first: [0]=+,[1]=-
name: +
   isNull: false
   isTerminal: true
   first: [0]=+
name: -
   isNull: false
   isTerminal: true
   first: [0]=-
name: R
   isNull: false
   isTerminal: false
   first: [0]=i,[1]=n,[2]=(,[3]=c
name: Om
   isNull: false
   isTerminal: false
   first: [0]=*,[1]=/
name: *
   isNull: false
   isTerminal: true
   first: [0]=*
name: /
   isNull: false
   isTerminal: true
   first: [0]=/
name: c
   isNull: false
   isTerminal: true
   first: [0]=c
name: Or
   isNull: false
   isTerminal: false
   first: [0]==,[1]=<,[2]=>,[3]=<=,[4]=>=
name: =
   isNull: false
   isTerminal: true
   first: [0]==
name: <
   isNull: false
   isTerminal: true
   first: [0]=<
name: >
   isNull: false
   isTerminal: true
   first: [0]=>
name: <=
   isNull: false
   isTerminal: true
   first: [0]=<=
name: >=
   isNull: false
   isTerminal: true
   first: [0]=>=
name: Ml0
   isNull: true
   isTerminal: false
   first: [0]=module,[1]=e
name: Vl0
   isNull: true
   isTerminal: false
   first: [0]=V,[1]=e
name: Il0
   isNull: true
   isTerminal: false
   first: [0]=,,[1]=e
name: Sl0
   isNull: true
   isTerminal: false
   first: [0]=e,[1]=begin,[2]=;,[3]=i,[4]=if,[5]=loop,[6]=exit,[7]=read,[8]=write
Press any key to continue








                                 back.gif (341 bytes)       up.gif (335 bytes)         next.gif (337 bytes)