what is the difference between lex and yacc

Manik Mahajan picture Manik Mahajan · Jul 27, 2009 · Viewed 43.5k times · Source

I have worked with lex for executing some code whenever some regular expression is found, Can Yacc do something more than that? If yes, then what?

Answer

Daniel C. Sobral picture Daniel C. Sobral · Jul 27, 2009

Yes, YACC is a parser, Lex is a lexical analyzer. They are typically used together: you Lex the string input, and YACC the tokenized input provided by Lex.

Now, a regular expression can only represent regular languages. One of the constraints of a regular language is the lack of "memory". You cannot define the rules for acceptance further down the string based on what has come before.

This is mostly clearly seen in the case of parenthesis. A regular language can't match nested parenthesis to the correct level. Or any other such structure. The grammars of (most) computer languages can and do, and, because of that, they can't be be parsed with a Lexer or a regular expression. That's where YACC comes in.

One can reverse the question as well. If YACC can do more, why not use it for the lexical analysis? Well, it so happens that you can verify the validity of a regular expression very efficiently, which is not the case of general grammars -- not to the same level. Still, YACC can do basic lexical analysis, if the lexical rules of the language are simple enough.