please show completed code in Java: Implementation of a topdown parser usuing a
ID: 3703631 • Letter: P
Question
please show completed code in Java:
Explanation / Answer
implementation of LL[1] parser.
import java.util.*;
import java.io.*;
public class LL {
public char[] expression;
/*
The current index.
*/
public int position;
/*
The stack used to store the LR states.
*/
public Stack stack;
/*
The current context-free grammar.
*/
public Grammar G;
/*
The input alphabet;
*/
public Alphabet alphabet;
/*
The LL(1) table.
*/
int[][] LLTable;
/*
Advance one character to the right on input.
*/
public void advance(){
position++;
}
/*
Returns the current token of the input. Discards possible
space characters.
*/
public short current(){
while(expression[position] == ' ')
advance();
char c = expression[position];
return (Character.isDigit(c))?
alphabet.toShort('c') : alphabet.toShort(c);
}
/*
Pop the left side of production <code>n</code> and push the right side .
*/
public void push(int n){
stack.pop();
Production[] P = G.productionsArray;
short[] right = alphabet.toShort(P[n].right);
int le = right.length;
for(int i = le - 1; i >= 0; i--)
stack.push(new Short(right[i]));
}
/*
Cancels the current character with the top of stack.
*/
public void cancel(){
advance();
stack.pop();
}
/*
True if the input has been read completely.
*/
public boolean endOfInput(){
return position == expression.length;
}
/*
Creates the <code>LLTable</code> and initializes the stack.
*/
public LL(String exp, Grammar grammar){
G = grammar;
alphabet = G.alphabet;
try{
LLTable = LLTable();
} catch (Exception e){
System.out.println(e);
System.exit(1);
}
expression = exp.toCharArray();
stack = new Stack();
char v = G.productionsArray[G.initial].left;
stack.push(new Short(alphabet.toShort(v)));
}
/*
The LL(1) table analysis. The entry <code>table[v][c]</code>
is the rule to
apply if the variable <code>v</code> is on the stack and
<code>v</code> is the lookahead value.
return the LL(1) table
*/
public int[][] LLTable() throws Exception {
int[][] table=new int[G.variables.size()][G.terminals.size()];
//initialize LL table
for(int i = 0; i < G.variables.size(); i++)
for(int j = 0; j < G.terminals.size(); j++)
table[i][j] = -1;
for(int i = 0; i < G.nbProductions; i++){
short[] r = G.alphabet.toShort(G.productionsArray[i].right);
short v = G.variables.toShort(G.productionsArray[i].left);
if(r.length > 0){
Set s = G.first(r);
for(Iterator it = s.iterator(); it.hasNext(); ) {
int u = ((Short) it.next()).shortValue();
if(table[v][u] != -1){
System.out.print("Conflict between rules" +i+" and "+
table[v][u]);
throw new Exception("The grammar is not LL(1)");
}
else
table[v][u] = i;
}
}
if(r.length == 0) { //rule i is an epsilon rule
Set f = G.follow(v);
for(Iterator it = f.iterator(); it.hasNext(); ){
short u = ((Short) it.next()).shortValue();
if(table[v][u] != -1){
System.out.print("Conflict between rules " +i+" and "+
table[v][u] + "for u ="
+G.terminals.toChar(u));
throw new Exception("The grammar is not LL(1)");
}
else
table[v][u] = i;
}
}
}
return table;
}
/*
Parses the input expression using the LL(1) analysis alpgorithm.
*/
public void lLParse() throws Exception {
System.out.println(stack);
while(true){
if(stack.isEmpty())
if(endOfInput()){
System.out.println("input accepted ");
break;
}
else
throw new Exception("Syntax error: end of input");
short c = current();
short v = ((Short) stack.peek()).shortValue();
if(G.terminals.isIn(alphabet.toChar(v)))
if(v == c) {
cancel();
System.out.println(stack);
}
else throw new Exception("Syntax error");
else {
v = G.alphabet.convert(G.variables, v);
int n = LLTable[v][alphabet.convert(G.terminals,c)];
if(n != -1){
push(n);
System.out.println(stack);
}
else throw new Exception("Syntax error");
}
}
}
static void printTable(String s,int[][] table){
System.out.println(s);
for(int i = 0; i < table.length; i++){
System.out.print(i+" ");
for(int j = 0; j < table[i].length; j++)
System.out.print(table[i][j]+" ");
System.out.println();
}
}
public static void main(String[] args) throws IOException {
String exp = args[0]+'$';
LL input = new LL(exp, Grammar.fromFile(args[1]));
try{
input.LLParse();
}catch(Exception e){
System.out.println(e);
System.exit(1);
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.