What's a parser? ... and computer "languages"

[Harut]

thanks a lot, Sip.

 

so does "parse" mean in the sense of that problem i had?

 

just separate/group? or there is special meaning to it in that problem?

[Azat]

Harut jan, read about "FLEX and BISON" if you want to learn more about parsers. Be warned, this is when I pulled 90% of my hair out.

 

Sip you did a great job of explaining.

[Sip]

parse technically means to "separate/group" and assign a special meaning. With FLEX and BISION (also known as LEX and YACC), you have 2 components: the lexical analyzer (lexer) and the parser. Yacc actually stands for "yet another compiler compiler".

 

In the problems that you did, you were mainly being a lexical analyzer which is the first step of parsing. What you did with the part A, you would just go thorough and do some blind substitution (spit out a new line instead of space). But that is ok since your parsing task only required you to do that and you weren't asked to figure out some special meaning in the input.

 

In part B, your task was a bit more complicated since you had to recognize different parts of the input ... like the function name, parameters separated by comas, etc. If you were to write a FULL parser, you would somehow store the information which you read in the input in some sort of structure after parsing (like storing the function and method name separately followed by the parameters, each in separate variables). I don't know if you have learned about lists or trees yet, but that's what you would normaly use.

 

So basically, the "parsers" which you wrote were nothing but the lexical analyzer parts of a full parser. But that's ok since your assignment only required you to do that and nothing more.

[Sip]

... and Azat, I totally hear you on the pulling hair part! My undergrad compiler class project was one of the hardest things I have ever had to do. I have such amazing respect for compiler writers after that class!!!

 

Before that, I often would say things like "oh, we will let the compiler worry about that" (such as optimizations, debugging, etc) but now, I don't say that anymore cause I know what a pain in the neck it can be for the compiler writer.

 

But I have to say Lex/Yacc (flex/bison) are a couple of the most useful tools I have ever used on a computer. I really like them.

[Azat]

Well, that's why you are soon to be a PhD in CS and I am just a janitor at the local factory.

 

BTW, You're going to throw a party and invite all of us when you get the degree, right?

[Harut]

very interesting.

 

hmmmm. i'm thinking if i should change my major to CS.

[Sip]

I decided it's probably better to put this in a separate thread. Parsing is a term that can have a lot of meanings. In the general sense, computer science people use the term "parse" when referring to the process where you read and understand some formatted input in your program.

 

In the simplest cases, "formatted" input comes as a series of special "tokens" separated by "delimiters". If your program can go through the input and figure out which ones are the tokens and which ones are the delimiters, then it is basically a parser. An example may be a spellchecker program which recognized english words in a document. The tokens are any english word and the delimiters are space, punctuations, etc. If the parser finds something it doesn't recognize, it complains.

 

Parsers are the main "front end" to compilers. Whenever you write a program in a specific language, the parser goes through the program and tries to understand the "program parse tree". I can go into the details of this if you want to understand how REAL parsers work. In general, parsers are very complicated as they have to keep track of a lot of things at the same time.

 

For example, think of a 'C++' program. Depending on what part of the program you are in, you may or may not be able to use certain tokens and keywords. If you use the wrong token in the wrong place, the parser will come back with a syntax error, telling you that you either forgot a bracket, didn't have the right operator or delimiter, or used an invalid "keyword" in the wrong place. It has to basically keep track of EVERYTHING and know what is allowed where and what is not allowed.

 

All those rules are specified in the "grammar" of the language. Every language has grammar.

 

So basically, a parser is something that given a "language grammar", processes an input text according to the grammar rules.

 

Our computers can only process very special types of grammars so they will have a lot of trouble with something like english. But they can do VERY good with languages like C. The details in what is exactly the difference between the types of grammars is what you would learn in a "automata theory" course But I can give you some basic info about that too if you are interested. It's not as complicated to understand as it sounds at first!!!