LinuxQuestions.org
Download your favorite Linux distribution at LQ ISO.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices



Reply
 
Search this Thread
Old 08-20-2012, 12:08 PM   #1
rit
LQ Newbie
 
Registered: Feb 2012
Location: kanpur,india
Posts: 21

Rep: Reputation: Disabled
lex and yacc


hello everyone,
i am new to lex and yacc and finding difficulty in learning.
please suggest me some tutorial so that i can learn it from scratch.
 
Old 08-20-2012, 04:57 PM   #2
devnull10
Member
 
Registered: Jan 2010
Location: Lancashire
Distribution: Slackware Stable
Posts: 547

Rep: Reputation: 115Reputation: 115
It's difficult to say really without knowing how much knowledge you have on the fundamentals for which lex and yacc are used?
Do you have any experience and knowledge of regular expressions (lex) and of grammars (yacc)?

My suggestion to start off would be to write yourself a very small formal grammar. Something as simple as an "Adding Machine" which takes a set of numbers and adds then together with the + symbol. Although that sounds extremely simple, it will be more than enough of a challenge to a beginner. You can use lex to find the numbers and the addition symbol then push those into yacc to define an equation etc etc...

The whole field around this area can be pretty mind-boggling though - it depends what you want to use it for.
 
Old 08-20-2012, 05:01 PM   #3
tronayne
Senior Member
 
Registered: Oct 2003
Location: Northeastern Michigan, where Carhartt is a Designer Label
Distribution: Slackware 32- & 64-bit Stable
Posts: 3,120

Rep: Reputation: 818Reputation: 818Reputation: 818Reputation: 818Reputation: 818Reputation: 818Reputation: 818
There is a useful book, Lex & Yacc, 2nd ed., ISBN 978-1565920002 available at Amazon.com http://www.amazon.com/lex-yacc-Doug-...s=lex+%26+yacc in both paperback and Kindle editions.

I have the first edition and found it useful for learning the in's and out's of these tools.

Hope this helps some.
 
Old 08-20-2012, 07:00 PM   #4
Tinkster
Moderator
 
Registered: Apr 2002
Location: in a fallen world
Distribution: slackware by choice, others too :} ... android.
Posts: 23,005
Blog Entries: 11

Rep: Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903
Moved: This thread is more suitable in <PROGRAMMING> and has been moved accordingly to help your thread/question get the exposure it deserves.
 
Old 08-20-2012, 08:21 PM   #5
sundialsvcs
Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 5,455

Rep: Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172
I will second the notion that this book is a very good place to start. If you, say, basically know nothing at this point about regular expressions and/or the vagaries of LALR(1) grammars and parsing theory, then ... "you're going to take a sip from the firehose, and any firehose will do, but this book is a good one if you prefer ... as I do ... to sit down with a good book (and a good glass of fine wine or equally-fine Scotch, to sip either one).

Don't get buried in the theory, which comes too-quickly. Grab the "big picture." (The source-code is incomprehensible. ... but it works.)

If you have further comments or questions after doing your initial studies, feel free to ask here. We'll know.
 
Old 08-21-2012, 09:36 AM   #6
rit
LQ Newbie
 
Registered: Feb 2012
Location: kanpur,india
Posts: 21

Original Poster
Rep: Reputation: Disabled
well yes i have knowledge of regular expressions(used in sed and grep).
Actually i tried learning from O'reilly but i found difficulty beacuse examples are very big(everything is not explained).
 
Old 08-21-2012, 10:20 AM   #7
tronayne
Senior Member
 
Registered: Oct 2003
Location: Northeastern Michigan, where Carhartt is a Designer Label
Distribution: Slackware 32- & 64-bit Stable
Posts: 3,120

Rep: Reputation: 818Reputation: 818Reputation: 818Reputation: 818Reputation: 818Reputation: 818Reputation: 818
Well, regular expressions are... regular expressions; they're the same across pretty much every editor, shells (BASH, Bourne, Korn) and lex. So, you're already half-way there. This stuff we so love to use all came out of Bell Labs' smart guys who invented it to make the job of building and maintaining Unix easier and more predictable and reliable.

Keep in mind that many compilers, notably C, have been written using lex and yacc. Essentially, you use lex to create the logic for evaluating statements then hand the output of lex to yacc to generate C code that is compiled (the make utility, for example, "knows" how to generate an executable program from lex and yacc). There is heavy use of lex and yacc in, for example, AWK. If you obtain a the source code for AWK (from Brian Kernighan's (the K in AWK) at http://www.cs.princeton.edu/~bwk/, you can study how lex and yacc are used to generate the grammar and syntax; learn from the best, eh?

Getting over the hump of grasping just what lex and yacc are all about can be a challenge -- they're almost alien concepts and structures when compared to top-down programming perhaps in a way that going from a "normal" calculator to an RPN calculator can be a challenge (you don't really "think" in RPN, you think more in 2 x 2 = 4). lex is kind of like that. If you make the effort to study the book, the reward may be more than worth the work you put in -- these two tools can open up the world for you.

Anyway best of luck!
 
Old 08-21-2012, 10:58 AM   #8
theNbomr
LQ 5k Club
 
Registered: Aug 2005
Distribution: OpenSuse, Fedora, Redhat, Debian
Posts: 5,396
Blog Entries: 2

Rep: Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903
This Lex and Yacc Tutorial by Tom Niemann has always been a favorite of mine. The use of syntax trees in the examples there can contribute greatly to understanding, once you've started to develop a feel for the important concepts.

--- rod.

Last edited by theNbomr; 08-21-2012 at 11:01 AM.
 
Old 08-21-2012, 11:28 AM   #9
sundialsvcs
Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 5,455

Rep: Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172
Well, the above description is not strictly true ...

"Lex" is a scanner, sometimes called a "lexer." It grabs characters from a stream and forms them into "tokens." For example, the string:

if (a == b) { c = 4; }

... contains a total of (if I have counted properly...) 12 tokens:

'if' '(' <ident> '==' <ident> ')' '{' <ident> '=' <int_const> ';' '}'

"Lex" uses regular-expression technology.

"Yacc" is a parser generator. Using the stream of tokens as its input, the Yacc-generated parser ... which is a "C" subroutine ... would recognize the structure of this stream of 12 tokens, recognizing such things as <if_statemet>, <logical_expression>, <assignment_statement>. And also recognizing that the entire stream of tokens is syntactically valid for the grammar of "C."

"Yacc" allows that parser to be generated through the definition of rules, that is to say a "grammar," which formally defines what the incoming language is allowed to be, and what is to be done when various parts of it are recognized. The generated parser is known to be fast, and the parser-generating capability provided by Yacc is generic.

Yacc isn't the only parser out there. There are many others, including for example Bison.

Yacc is a shift/reduce parser, as most such algorithms are, and perhaps the first step for you ought to be to study the approach that's taken by this important algorithm. By that I mean, "when Yacc tells you that you have a 'shift/reduce conflict', what is it actually saying to you?" Likewise, the nature of the algorithm imposes certain strictures upon the language itself ... "but why?" (And don't just say "LALR(1).")

Last edited by sundialsvcs; 08-21-2012 at 11:35 AM.
 
Old 08-22-2012, 10:11 AM   #10
rit
LQ Newbie
 
Registered: Feb 2012
Location: kanpur,india
Posts: 21

Original Poster
Rep: Reputation: Disabled
thank you guys.....
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Lex and YACC under C++ namespace MTK358 Programming 1 04-23-2011 06:27 AM
lex and yacc aarsh Linux - Software 3 01-03-2011 09:58 AM
Lex and Yacc Information cmnorton Programming 4 11-04-2008 11:50 AM
LEX and YACC with C gr33ndata Programming 4 11-18-2007 06:12 PM
Lex and Yacc on Federo 2.0 vivekian Fedora 6 05-20-2006 10:09 AM


All times are GMT -5. The time now is 01:34 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration