Parenthesized Expression Recursive Descent Parser

1.5k views Asked by At

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 ?

0

There are 0 answers