How to understand lex and yacc
This article is about how to understand lex and yacc, the editor thinks it is very practical, so I share it with you to learn. I hope you can get something after reading this article.
I. background
Learn lex and yacc from scratch
1. Basics
Lex has only state and state transition, no stack, and is good at pattern matching; yacc can handle FSA (finite state machine) with stack, which is more suitable for more complex tasks.
Pattern matching primitive
Metacharacter
Match description
.
Any character (except newline)
\ n
New line
*
Repeat the previous expression 0 or more times
+
Repeat the previous expression one or more times
?
Repeat the previous expression 0 or 1 times
^
The beginning of the line
$
The end of the line
A | b
An or b
(ab) +
Repeat group ab one or more times
[...]
Any character that appears
Some examples of matching
Expression.
Match description
Abc
Abc
Abc*
Ab, abc, abcc, abccc,.
Abc+
Abc, abcc, baccc,.
A (bc) +
Abc, abcbc, abcbcbc,.
A (bc)?
A, abc
[abc]
A, b, c
[aMuz]
Any character from a to z
[a\-z]
A, -, z
[- az]
-, a, z
[a-zA-Z0-9] +
One or more of any numeric letters
[\ t\ n]
Witespace
[^ ab]
Any character except afort b
[a ^ b]
A, ^, b
[a | b]
A, |, b
A | b
An or b
Matching rules:
1. Greed: two patterns match the same string and match the longest pattern
two。 Order priority: two patterns of the same length that match the previously defined patterns
The format of the .l file content is divided into three parts by%%, as follows:
.... definitions.
%%
.rules....
%%
... subroutines...
Rules is required, and other parts are optional.
Some built-in functions and variables
Int yylex (void)
Call the parser and return token
Char * yytext
Specify a matching string
Yyleng
The length of the string on the match
Int yywrap (void)
If you return 1, it's over.
FILE * yyout
Output file, default stdout
FILE * yyin
Input file, default stdin
INITIAL
Initial start conditionBEGIN condition
Switch start condition
ECHO
Write mached string
# define ECHO fwrite (yytext, yyleng, 1, yyout)
Second, start with the first example
Environment description:
VMware Workstation 12 Pro, ubuntu17.04, lex2.6.1
Output the contents of the file and add the line number before it
Lineno.l
% {int yylineno;%}% ^ (. *)\ n printf ("% 4d\ t% s", + + yylineno, yytext);% int main (int argc, char * argv []) {FILE * fp = NULL; if (argc = 2) {fp = fopen (argv [1], "r"); if (NULL! = fp) {yyin = fp;}} yylex () If (NULL! = fp) {fclose (fp);} return 0;}
Use lex to convert lineno.l files to .c files
$lex lineno.l $ls lex.yy.c lineno.l
Use gcc to compile lex.yy.c into an executable file
$gcc lex.yy.c-o lineno
/ tmp/ccNgesbZ.o: in the function 'yylex':
Lex.yy.c: (.text + 0x55c): undefined reference to 'yywrap'
/ tmp/ccNgesbZ.o: in the function 'input':
Lex.yy.c: (.text + 0x116c): undefined reference to 'yywrap'
Collect2: error: ld returned 1 exit status
It is said that the online query is to implement the yywrap function in .l file.
After modification:
% {int yylineno;%}% ^ (. *)\ n printf ("% 4d\ t% s", + + yylineno, yytext);% int main (int argc, char * argv []) {FILE * fp = NULL; yylineno = 0; if (argc = = 2) {fp = fopen (argv [1], "r"); if (NULL! = fp) {yyin = fp }} yylex (); if (NULL! = fp) {fclose (fp);} return 0;} int yywrap () {return 1;}
Compile successfully again
$gcc lex.yy.c-o lineno$lineno lineno.l
1% {
2 int yylineno
3%}
four
5%
6 ^ (. *)\ nprintf ("% 4d\ t% s", + + yylineno, yytext)
7%
eight
9 int main (int argc, char * argv [])
10 {
11 FILE * fp = NULL
12 yylineno = 0
thirteen
14 if (argc = = 2) {
15 fp = fopen (argv [1], "r")
16 if (NULL! = fp) {
17 yyin = fp
18}
19}
twenty
21 yylex ()
twenty-two
23 if (NULL! = fp) {
24 fclose (fp)
25}
twenty-six
27 return 0
28}
twenty-nine
30 int yywrap ()
31 {
32 return 1
33}
The above is how to understand lex and yacc. The editor believes that there are some knowledge points that we may see or use in our daily work. I hope you can learn more from this article. For more details, please follow the industry information channel.
