[DaMi25]

Hello. I really need a big help on my case study.. I'm still at my 2nd year in college and my professor in our IT Elective subject who have just arrived from Korea gave us a case study about Syntax Analyzer and I still have less than 2 weeks to figure it out before the semester ends. Our topic now is about Programming Language Abstraction and Parse Trees. What he wants us to do is that if we enter A := B * (A + C), the program will check if it is a valid or invalid. If it is valid, it follows the grammar and it will show the parse tree of the statement but for invalid, it will show nothing except an error message. He also wants us to make a GUI of the program. We're just starting out with Swing, we skipped File Input and Output. Please help me out.. I need to do this because that professor of ours is a strict one and has no mercy..

Example: A Grammar for Simple Assignment Statement
<assign> -> <id> := <expr>
<id> -> A|B|C
<expr> -> <id> + <expr>
<id> * <expr>
(<expr>)
<id>
A:= B * (A+C)

<assign> => <id> := <expr>
=> A:= <expr>
=> A:= <id> * <expr>
=> A:= B * <expr>
=> A:= B *(<expr>)
=> A:= B * (<id> + <expr>)
=> A:= B * (A + <expr>)
=> A:= B * (A + <id>)
=> A:= B * (A + C)

[GregBrannon]

What have you tried? Apart from links to possibly helpful tutorials or similar topics, there's not a lot we can do to help you. You'll get more help by showing some effort and asking for help to improve what you've done and/or fix the problems you've encountered.

[DaMi25]

GregBrannon, on 10 March 2013 - 10:51 AM, said:

What have you tried? Apart from links to possibly helpful tutorials or similar topics, there's not a lot we can do to help you. You'll get more help by showing some effort and asking for help to improve what you've done and/or fix the problems you've encountered.

I'm sorry. The problem is, I don't know where to go, how to start.. May you suggest some links about creating a Syntax Analyzer if you know some? Thanks..

[GregBrannon]

Here's an essay of considerations with some sample code.

Try searching "compiler design," "expression parser," etc.

[FallenG]

I an not entirely clear on what you are trying to do... are you trying to write a syntactic analyser for a simple language?

You can have a look at Yacc, it is a tool which takes in a grammar and produces a syntactic analyser for it (if it can). If you have to write one yourself, there should be a lot of good documentation online about how to write SLR/LALR parser: conceptually they are relatively simple.

[DaMi25]

GregBrannon, on 10 March 2013 - 02:08 PM, said:

Here's an essay of considerations with some sample code.

Try searching "compiler design," "expression parser," etc.

Thank you Greg. Gonna try it.

[DaMi25]

FallenG, on 10 March 2013 - 02:26 PM, said:

I an not entirely clear on what you are trying to do... are you trying to write a syntactic analyser for a simple language?

You can have a look at Yacc, it is a tool which takes in a grammar and produces a syntactic analyser for it (if it can). If you have to write one yourself, there should be a lot of good documentation online about how to write SLR/LALR parser: conceptually they are relatively simple.

Not for a language. It just checks the grammar if it is valid or invalid. For example, this one is an example of a correct grammar. A := B*(C+. An invalid grammar is this, A:==B*(C+. As you can see, the equal sign was doubled so it will be invalid because the right one after a single equal sign is an <id>. <id> = A|B|C|D. Is it okay now?

[FallenG]

DaMi25, on 10 March 2013 - 04:16 PM, said:

FallenG, on 10 March 2013 - 02:26 PM, said:

I an not entirely clear on what you are trying to do... are you trying to write a syntactic analyser for a simple language?

You can have a look at Yacc, it is a tool which takes in a grammar and produces a syntactic analyser for it (if it can). If you have to write one yourself, there should be a lot of good documentation online about how to write SLR/LALR parser: conceptually they are relatively simple.

Not for a language. It just checks the grammar if it is valid or invalid. For example, this one is an example of a correct grammar. A := B*(C+/>/>. An invalid grammar is this, A:==B*(C+/>/>. As you can see, the equal sign was doubled so it will be invalid because the right one after a single equal sign is an <id>. <id> = A|B|C|D. Is it okay now?

A grammar defines a language (so "A := B" is in the language, but "A :== B" is not in the language).

You do not want to check if the grammar is valid, but if a given list of tokens (such as "A := B") can be produced by the grammar: i.e. is in the language. This might seem like an overly pernickety point, but there is a whole other topic which covers checking grammar validity, and you should not confuse the two.

Again, I recommend looking at Yacc and its implementation. It is an example of an LR parser, a standard way of doing what you want to do.

[DaMi25]

Coded by a friend of mine.
Say something about this program:

import java.util.Scanner;
import java.util.Stack;


public class Parser {
Scanner in=new Scanner(System.in);
int k=0;
 public Parser() {
  // TODO Auto-generated constructor stub
  System.out.println("Please Enter the Simple Assignment");
  String s=in.nextLine();
  Stack st=new Stack();
  for(int i=0;i<s.length();i++)
    st.push(s.charAt(i));
  if(s.length()!=10)
  {
    System.out.println( " You Entered "+s+"  which is"+" Syntactically FALSE");
    System.exit(0);
  }
  
  if(st.peek().toString().equals(")"))
    k++;
  st.pop();
  String c=  st.peek().toString();
  if(c.equals("A")||c.equals("B")||c.equals("C"))
    k++;
  st.pop();
   
     c=(String) st.peek().toString();
  if(c.equals("+"))
    k++;
  st.pop();
  
    c=(String) st.peek().toString();
  if(c.equals("A")||c.equals("B")||c.equals("C"))
    k++;
  st.pop(); 
  
  c=(String) st.peek().toString();
  if(c.equals("("))
    k++;
  st.pop();
  c=(String) st.peek().toString();
  if(c.equals("*"))
    k++;
  st.pop();
  
    c=(String) st.peek().toString();
   if(c.equals("A")||c.equals("B")||c.equals("C"))
     k++;
   st.pop(); 
  
  c=(String) st.peek().toString();
  if(c.equals("="))
    k++;
  st.pop();
  c=(String) st.peek().toString();
  if(c.equals(":"))
    k++;
  st.pop();
    c=(String) st.peek().toString();
   if(c.equals("A")||c.equals("B")||c.equals("C"))
     k++;
   st.pop();
   
   
   if(k==s.length())
     System.out.println( " You Entered "+s+"  which is"+" Syntactically TRUE");
   else 
     System.out.println( " You Entered "+s+"  which is"+" Syntactically FALSE");
    
 }

 /**
  * @param args
  */
 public static void main(String[] args) {
  // TODO Auto-generated method stub
    new Parser();
 }

}

[FallenG]

It is common to split the lexical analysis (turning source code, as a string, into a stream of tokens) from the syntactic analysis (producing a parse tree).
Splitting it into two passes significantly simplifies each pass.

Example:

{source code}

A := B + C

{lexical analysis}

(IDENTIFIER "A"),
ASSIGN,
(IDENTIFIER "B"),
(BINARY_OPERATOR PLUS),
(IDENTIFIER "C")

{syntactic analysis}

  ASSIGN
  /    \ 
 A    BINOP PLUS 
      /   \
     B     C

Wikipedia's page on Parsing says pretty much the same thing, in different words.

EDIT:
At first glance, your friend seems to have written something which only recognises the exact input they gave. There are actually much simpler ways of doing that, but that isn't a parser. That is just checking if the input is "A:=B+C" after removing irrelevant characters.

This post has been edited by FallenG: 11 March 2013 - 07:55 AM

[DaMi25]

FallenG, on 11 March 2013 - 02:53 PM, said:

It is common to split the lexical analysis (turning source code, as a string, into a stream of tokens) from the syntactic analysis (producing a parse tree).
Splitting it into two passes significantly simplifies each pass.

Example:

{source code}

A := B + C

{lexical analysis}

(IDENTIFIER "A"),
ASSIGN,
(IDENTIFIER "B"),
(BINARY_OPERATOR PLUS),
(IDENTIFIER "C")

{syntactic analysis}

  ASSIGN
  /    \ 
 A    BINOP PLUS 
      /   \
     B     C

Wikipedia's page on Parsing says pretty much the same thing, in different words.

EDIT:
At first glance, your friend seems to have written something which only recognises the exact input they gave. There are actually much simpler ways of doing that, but that isn't a parser. That is just checking if the input is "A:=B+C" after removing irrelevant characters.

First of all, thank you because until now, you're giving time in replying on my thread.
Please continue on helping me. So what you mean is that the program written by my friend is not a right way? I can't think of how will I check each token. I know that the program written by my friend is only for letters A - C that's why it's not flexible. When you enter letter D, it will result to invalid. What will I do then? Please give me some more tips and ideas because I haven't started coding yet. I don't know where to start.

[DaMi25]

Look at this. Is this a right way of breaking the string into tokens?

import java.util.*;

public class ParserTry
{
  public static void main(String[] args)
  {
    
    String test = "A:=B+C";
    char[] token = test.toCharArray();
    
    for(int i = 0;i<token.length;i++)
      System.out.println(token[i]);
    
  }
}