Programming Forums > Application Development > C++

programmingnoob · Apr 26th, 2006, 4:56 PM

so i have the scanner ready ... and now i am supposed to write a parser

so i have two questions

1) how does the scanner help the parser? let me get the process straight ... my scanner looks at each character and then returns a token .... so is parser now going to look at that token and somehow store it somewhere and then take the next token and keeps getting the next token until the end of line or something? and then form a parse tree and print it?
and if the expression makes no sense, then print error or something like that?

2) How do I incorporate BNF in the entire process? what do i do with it? is BNF supposed to tell me whether the given expression is valid or not?

(i'm sure i will have lots of doubts when i actually start coding)

nnxion · Apr 26th, 2006, 5:34 PM

Might wish to read a piece on Lex and Yacc. Lex and Yacc are tools used to generate lexical analyzers and parsers.

The Dark · Apr 26th, 2006, 5:56 PM

If the assignment is to write a parse, I am not sure that getting a program to generate one for you would be good enough.

You pretty much seem on track, programmingnoob. The parser takes tokens from the scanner and then processes them to see if there is a valid expression. IMO "Recursive Descent Parsers" are the easiest to write.

programmingnoob · Apr 27th, 2006, 12:00 AM

Quote:

Originally Posted by The Dark

If the assignment is to write a parse, I am not sure that getting a program to generate one for you would be good enough.

You pretty much seem on track, programmingnoob. The parser takes tokens from the scanner and then processes them to see if there is a valid expression. IMO "Recursive Descent Parsers" are the easiest to write.

sorry! I forgot to mention .. i am supposed to write a recursive descent parser

programmingnoob · May 26th, 2006, 6:53 PM

i fell sick, so i took a break from the assignments
i'm really confused ...
even though i am supposed to generate parser trees, for now, let's suppose i am supposed to create a yes/no parser, meaning it just checks whether the expression is valid or not.
consider the rule below
<compound> ::= begin <stmt-list> end

^^ how would you write code for this particular rule? I believe if you write pseudocode for just one rule, i'll get the idea.

i have the scanner ready, it looks at a stream of text and returns tokens ... please ask me if this is not clear.

also, if you do not want to write the code, then that is totally understandable

(I'm writing a recursive descent parser)

programmingnoob · May 27th, 2006, 8:31 PM

Quote:

Originally Posted by The Dark

If the assignment is to write a parse, I am not sure that getting a program to generate one for you would be good enough.

You pretty much seem on track, programmingnoob. The parser takes tokens from the scanner and then processes them to see if there is a valid expression. IMO "Recursive Descent Parsers" are the easiest to write.

is the scanner supposed to preserve the order of the tokens?

Harakim · May 27th, 2006, 10:02 PM

If you don't mind me asking, how do you know what you are compiling from and what you are compiling to? Are you making a general purpose compiler?

The Dark · May 28th, 2006, 9:06 AM

Quote:

Originally Posted by programmingnoob

is the scanner supposed to preserve the order of the tokens?

Yes, otherwise the parser won't be able to make any sense of the symbols.

programmingnoob · May 28th, 2006, 10:43 PM

Quote:

Originally Posted by The Dark

Yes, otherwise the parser won't be able to make any sense of the symbols.

exactly

but what if you pass the token to parser as soon as it is generated by the scanner?
here's the pseudo-code given by my professor, which doesnt make much sense to me except they scan the text stream only when it's needed

the code is for the function for the rule: <id-list> ::= $id | <id-list> , $id

(Toggle Plain Text)

if NT->attr =! id, then return NULL.
i = cons (NULL, NT, NULL); 
NT = Sc.get(); 
while (NT->attr == ,) do
j = NT
NT = Sc.get();
if NT->attr =!id, then return Null. 
cons (i, j, cons (NULL) NT, NULL);
NT->attr =! id, then return NULL
cons (i, j, cons (NULL, NT, NULL);
NT = Sc.get();
return (i);

NT means next token
if you have any idea what i = cons... etc mean, please let me know

b1g4L · Apr 26th, 2006, 9:39 PM

Are you just trying to break up a string into substrings by spaces?

Apr 26th, 2006, 4:56 PM	#1
programmingnoob Hobbyist Programmer Join Date: Feb 2006 Posts: 155 Rep Power: 3	writing a parser in c++ so i have the scanner ready ... and now i am supposed to write a parser so i have two questions 1) how does the scanner help the parser? let me get the process straight ... my scanner looks at each character and then returns a token .... so is parser now going to look at that token and somehow store it somewhere and then take the next token and keeps getting the next token until the end of line or something? and then form a parse tree and print it? and if the expression makes no sense, then print error or something like that? 2) How do I incorporate BNF in the entire process? what do i do with it? is BNF supposed to tell me whether the given expression is valid or not? (i'm sure i will have lots of doubts when i actually start coding)

Apr 26th, 2006, 5:34 PM	#2
nnxion Programming Guru Join Date: Jun 2005 Location: elemental plane Posts: 1,429 Rep Power: 5	Might wish to read a piece on Lex and Yacc. Lex and Yacc are tools used to generate lexical analyzers and parsers. __________________ "Employ your time in improving yourself by other men's writings, so that you shall gain easily what others have labored hard for." -- Socrates

Thread Tools
Show Printable Version Email this Page
Display Modes
Switch to Linear Mode Hybrid Mode Switch to Threaded Mode

Apr 26th, 2006, 5:56 PM	#3
The Dark Expert Programmer Join Date: Jun 2005 Posts: 893 Rep Power: 4	If the assignment is to write a parse, I am not sure that getting a program to generate one for you would be good enough. You pretty much seem on track, programmingnoob. The parser takes tokens from the scanner and then processes them to see if there is a valid expression. IMO "Recursive Descent Parsers" are the easiest to write.

May 26th, 2006, 6:53 PM	#5
programmingnoob Hobbyist Programmer Join Date: Feb 2006 Posts: 155 Rep Power: 3	i fell sick, so i took a break from the assignments i'm really confused ... even though i am supposed to generate parser trees, for now, let's suppose i am supposed to create a yes/no parser, meaning it just checks whether the expression is valid or not. consider the rule below <compound> ::= begin <stmt-list> end ^^ how would you write code for this particular rule? I believe if you write pseudocode for just one rule, i'll get the idea. i have the scanner ready, it looks at a stream of text and returns tokens ... please ask me if this is not clear. also, if you do not want to write the code, then that is totally understandable (I'm writing a recursive descent parser)

May 27th, 2006, 10:02 PM	#7
Harakim Hobbyist Programmer Join Date: May 2006 Location: West Jordan, Utah, United States Posts: 176 Rep Power: 3	If you don't mind me asking, how do you know what you are compiling from and what you are compiling to? Are you making a general purpose compiler?

Apr 26th, 2006, 9:39 PM	#10
b1g4L Programmer Join Date: Dec 2005 Location: SC Posts: 38 Rep Power: 0	Are you just trying to break up a string into substrings by spaces?

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > C++

writing a parser in c++