Lex/YACC Question

MTK358 · 03-25-2010, 03:17 PM

Quote:

Originally Posted by smeezekitty

GCC is written with L&Y.

AFAIK GCC's parser is written by hand (correct me if I'm wrong).

smeezekitty · 03-25-2010, 03:19 PM

Download GCC source and you will see there is .l and .y files.

MTK358 · 03-25-2010, 03:21 PM

I guess I will download GCC's source and see. I might learn something from it, too.

smeezekitty · 03-25-2010, 03:38 PM

Attached.

Sergei Steshenko · 03-25-2010, 04:02 PM

Quote:

Originally Posted by MTK358

Still,

what is so bad about Lex and YACC?

OK, so they use tokens, but as long as you can easily pass their semantic value, who really cares? And even so, that's not my main problem, which is the AST (which exists no matter what parser you use).

The bad thing about lex and yacc is that they make me think unnaturally using entities beyond the necessary.

Another bad things is that they hide from me the relationship between language constructs and callbacks.

The AST is not a problem when you construct it.

MTK358 · 03-25-2010, 04:08 PM

Quote:

Originally Posted by Sergei Steshenko

The AST is not a problem when you construct it.

Even with Lex/YACC, you still construct the AST.

I tried writing my own parser, and not only did you have to deal with the AST the same amound as with Lex/YACC, you still have to worry about dealing with precedence, etc.

Sergei Steshenko · 03-25-2010, 04:22 PM

Quote:

Originally Posted by MTK358

Even with Lex/YACC, you still construct the AST.
...
you still have to worry about dealing with precedence, etc.

Yep - in Perl a hash deals with them nicely. I.e. my piece of code parsing expressions uses such a hash/table, so not a problem to add an operation with its precedence.

MTK358 · 03-25-2010, 04:24 PM

The problem is not in knowing the precedence of the operator, but implementing it.

At the very least, is there some simple explanation on the Internet of how the parsing algorithm works?

Sergei Steshenko · 03-25-2010, 04:47 PM

Quote:

Originally Posted by MTK358

The problem is not in knowing the precedence of the operator, but implementing it.

At the very least, is there some simple explanation on the Internet of how the parsing algorithm works?

About implementing precedences - look for

expression parsing
.

About parsing algorithm - you are starting from a wrong end. Take a piece of paper and/or a text file and describe actions your eyes and your finger(s) perform when you formally analyze a piece of code.

FWIW, fingers are very good analogues of pointers - I am serious.

Again, describe in in plain English how you come to the conclusion that in, say,

Code:

abc = def;
fgh = 123;
xcv = ();

the first two lines/entities are correct and the third is wrong.

MTK358 · 03-25-2010, 04:53 PM

Because there is no rule that includes parens except for a function call, where an inentifier is supposed to precede them.

Sergei Steshenko · 03-25-2010, 05:04 PM

Quote:

Originally Posted by MTK358

Because there is no rule that includes parens except for a function call, where an inentifier is supposed to precede them.

How did you arrive to the last line in the first place ? I.e. what did you do exactly to read the last line in the first place ?

Forget about rules you are giving to a tool made by somebody else. Start from scratch.

Assume that

Code:

abc = def;

is called identifier_to_identifier_assignment and that

Code:

fgh = 123;

is called number_to_identifier_assignment - can you write a piece of code that would recognize these two constructs and print their names ?

And then how would you formulate the error message regarding

Code:

xcv = ();

?

smeezekitty · 03-25-2010, 05:29 PM

xcv = (); does not necessarily have to be an error, () could be assumed to be 0.

Sergei Steshenko · 03-25-2010, 05:33 PM

Quote:

Originally Posted by smeezekitty

xcv = (); does not necessarily have to be an error, () could be assumed to be 0.

In my set of rules it's an error. Period.

MTK358 · 03-25-2010, 07:31 PM

There is a reason people don't write computer code (grammars included) in English.

Sergei Steshenko · 03-25-2010, 07:39 PM

Quote:

Originally Posted by MTK358

There is a reason people don't write computer code (grammars included) in English.

Unless you can explain it in plain English, you can't do it.

Unless you can explain it in English, you can't file a bug against parser/compiler.

Again, think what you are doing with your eyes and fingers in order to check the validity of the

Code:

abc = def;
fgh = 123;
xcv = ();

example.

One short explanation from a professional programmer without any complex formalities was sufficient for me to understand how parsers are implemented. The explanation was essentially in terms of eyes/fingers.

In general, we, humans, are not that stupid compared to computers. I.e. often it is just sufficient to express in code what we normally can explain in plain English as our eyes + fingers actions.