For grammar rules listed below , I want to write a recursive descent parser :
Expression -> Digit | '(' Expression Op Expression ')'
Op -> +|*
Digit -> 0|1|2|3|4|5|6|7|8|9
So I have Used the below C# code :
public class Expression
{
public Expression(){}
//Note: The Form 2 Grammar , Expression Structre
public char type;//parenthesized or digit
public int value;
public Expression left;
public char op;
public Expression right ;
}
public class Token
{
public Token() { }
public char type;
public char value;
}
int current=-1;
Token token;
public class Form1:Form
{
public Form1()
{
InitializeComponent();
token = new Token();
}
private void Get_Next_Token()
{
int n = richTextBox1.Text.Length;
char ch;
current++;
if (current < n)
{
ch = richTextBox1.Text[current];
if (0 <= ch-'0' && ch-'0' <= 9)
token.type = 'D';
else
token.type = ch;
token.value = ch;
}
}
private int Parse_Operator(ref char op)
{
if (token.type == '*' || token.type == '+')
{
op = token.type;
Get_Next_Token();
return 1;
}
Get_Next_Token();
return 0;
}
private int Parse(ref Expression expr_p)
{
Expression expr = expr_p = new Expression();
if (token.type == 'D')
{
expr.value = token.value - '0';
expr.type = 'D';
Get_Next_Token();
return 1;
}
if (token.type == '(')
{
expr.type = 'P';
Get_Next_Token();
if (Parse(ref expr.left) == 0)
{
Error("Missing Left expression");
}
if (Parse_Operator(ref expr.op) == 0)
{
Error("Missing Operator");
}
if (Parse(ref expr.right) == 0)
{
Error("Missing Right Expression");
}
if (token.type != ')')
{
Error("Missing )");
}
Get_Next_Token();
return 1;
}
return 0;
}
private void Error(string msg)
{
listBox1.Items.Add(msg);
}
private void button2_Click(object sender, EventArgs e)
{
Expression parenthesized_expr = new Expression();
//Reset
current = -1;
////***End Reset
Get_Next_Token();
listBox1.Items.Clear();
if (token.value == '(')
{
Parse(ref parenthesized_expr);
//listBox1.Items.Add("Build Succeeded");
}
else
{
Error("Missing Initial (");
}
}
}
Parser Works Great For somthing like (2+3) but not working for (3+(2+4)*4)
So how can I make parser to parse the expression until last ?