# Lex and Yacc

[resource link](https://lafibre.info/images/doc/201705_lex_yacc_tutorial.pdf)

## Lex

把輸入(strings)轉換成tokens

- 常見regex

| Metachrater | Matches |
| --- | --- |
| . | 除了newline的所有字元 |
| \n | newline |
| * | 0或多個 |
| + | 1或多個 |
| ? | 0或1個 |
| ^ | beginning of line |
| $ | end of line |
| a|b | |

範例

abc*⇒ab, abc, abcc...

abc+⇒abc, abcc...

a(bc)+⇒abc,abcbc...

[^ab]⇒除了ab的所有東西

[a^b]⇒a或^或b

... definitions ...
%%
... rules ...
%%
... subroutines ...

- 內建function和變數

    1. ECHO 印出rule讀到的東西，相當於
    	#define ECHO fwrite(yytext, yyleng, 1, yyout)
    2. yytext rule對應到的字串
    3. yyleng yytext的長度

- 範例1：印出所有東西

    %%
        /* match everything except newline */
    .   ECHO;
        /* match newline */
    \n  ECHO;
    %%
    int yywrap(void) {
    	return 1;
    }
    
    int main(void) {
    	yylex();
    	return 0;
    }

- 範例2：使用definitions

    digit    [0-9]
    letter   [A-Za-z]
    %{
    	int count;
    %} 
    %%
    /* match identifier */
    {letter}({letter}|{digit})*    count++;
    %%
    int main(void) {
    	yylex();
    	printf("number of identifiers = %d\n", count); 
    	return 0;
    }

## Yacc

Grammars採用Backus Naur Form(BNF)的變種（我也不知道是什麼），用來使用在context-free的語言上

... definitions ...
%%
... rules ...
%%
... subroutines ...

- token宣告

    %token INTEGER
    %left '+' '-'
    %left '*' '/' // 優先權由下而上

- 範例1 %token

.y

    %token INTEGER

換產出y.tab.h

    #ifndef YYSTYPE
    #define YYSTYPE int
    #endif
    #define INTEGER 258
    extern YYSTYPE yylval;

lex就可以把他回傳給yacc檔

.l

    [0-9]+    {
                    yylval = atoi(yytext);
                    return INTEGER; 
    		    }

把yytext轉乘int存到yylval，再回傳到yacc裡的INTEGER token

yylval的型別內定是integer。

- 範例2 簡單加減法，直接回傳字元到yacc

在.l中，直接回傳字元

    [-+]         return *yytext;        /* return operator */

    %{
    		#include <stdio.h>
        int yylex(void);
        void yyerror(char *);
    %}
    %token INTEGER
    %%
    program:
        program expr '\n'       { printf("%d\n", $2); }
        |
        ;
    expr:
        INTEGER                 { $$ = $1; }
        | expr '+' expr         { $$ = $1 + $3; }
        | expr '-' expr         { $$ = $1 - $3; }
        ;
    %%
    void yyerror(char *s) {
        fprintf(stderr, "%s\n", s);
    }
    
    int main(void) {
        yyparse();
        return 0;
    }

- 範例3 使用union 和%type<nPtr>

.y這樣寫

    %union {
        int iValue;         /* integer value */
        char sIndex;        /* symbol table index */
        nodeType *nPtr;     /* node pointer */
    };

會產生對應的y.tab.h

    typedef union {
        int iValue;         /* integer value */
        char sIndex;        /* symbol table index */
        nodeType *nPtr;     /* node pointer */
    } YYSTYPE;
    extern YYSTYPE yylval;

這裡有點難懂

    %token <iValue> INTEGER
    %type <nPtr> expr

把expr 綁成nPtr、INTEGER綁成union裡的iValue，如此一來就可以有以下的表達

    expr: INTEGER { $$ = con($1); } // 我不知道con是什麼..

> 我的理解nPtr是一個節點的概念，expr = expr+expr就是把兩個節點縮成一個節點
>