Lex and yacc은

   ·컴파일러 또는 인터프리터를 작성하기 위한 도구

   ·패턴을 찾기 위한 응용분야에서 사용하기 쉽다.

특징

    ·rapid prototyping

    ·easy modification

    ·simple maintenance

Lex 및 Yacc가 이용된 예

   ·desktop calculator bc

   ·typesetting tools eqn, pic, xfig

   ·C compilers PCC, GCC

   ·menu compiler

   ·A SQL processors

   ·the lex itself

 

 

Availability of Lex and Yacc

 

Yacc was the first of the two,developed by Stephen C.Johnson. Lex was designed to work with yacc by M.E.Lesk and E.Schmidt. Both lex and yacc have been standard UNIX utilities since Version 7, and no significant differences between Berkeley and System V versions.

 

AT&T version lex and yacc

BSD version Berkeley yacc

GNU bison

GNU flex

MS-DOS, OS/2 versions

 

1.Lex and Yacc

 

The Simplest Lex Program

 

간단한 lex입력

%%

.|\n           ECHO;

%%

UNIX의 cat과 같은 기능

lex에 의하여 생성된 프로그램

#include <stdio.h>

#include <stdlib.h>

# define U(x) x

중략

yylex(){

int nstr; extern int yyprevious;

#ifdef __cplusplus

/* to avoid CC and lint complaining yyfussy not being used ...*/

static int __lex_hack = 0;

if (__lex_hack) goto yyfussy;

#endif

while((nstr = yylook()) >= 0)

yyfussy: switch(nstr){

     case 0:

             if(yywrap()) return(0); break;

     case 1:

# line 2 "ch1-1.l"

             ECHO;

             break;

     case -1:

             break;

     default:

             (void)fprintf(yyout,"bad switch yylook %d",nstr);

   } return(0); }

/* end of yylex */

생략

 

lex specification의 구성

definition section

%%

rule section

        pattern(regular expression)     action(C source code)

%%

user subroutine section(C source code)

 

 

Lex로 단어 인식 프로그램 만들기

 

인식할 단어:

is        am        are       were

was     be         being    been

do       does      did        will

would  should  can        could

has     have     had        go

 

단어 인식기 - LEX SPEC.

%{

/*

 * this sample demonstrates (very) simple recognition:

 * a verb/not a verb.

 */

%}

%%

[\t ]+         /* ignore white space */ ;

is |

am |

are |

were |

was |

be |

being |

been |

do |

does |

did |

will |

would |

should |

can |

could |

has |

have |

had |

go             { printf("%s: is a verb\n", yytext); }

[a-zA-Z]+      { printf("%s: is not a verb\n", yytext); }

.|\n           { ECHO; /* normal default anyway */ }

%%

 

main()

{

        yylex();

}

 

 

코드생성 및 실행

% lex ch-01.l

% ls

lex.yy.c

% cc lex.yy.c -o first -ll

% ls

first  lex.yy.c

% first

did I have fun?

did: is a verb

I: is not a verb

have: is a verb

fun: is not a verb

?

^D

%

 

 

문장의 다른 단어도 인식하기 - LEX SPEC

 

%{

/*

 * We expand upon the first example by adding recognition of some other

 * parts of speech.

 */

%}

%%

[\t ]+         /* ignore white space */ ;

is |

am |

are |

were |

was |

be |

being |

been |

do |

does |

did |

will |

would |

should |

can |

could |

has |

have |

had |

go             { printf("%s: is a verb\n", yytext); }

very |

simply |

gently |

quietly |

calmly |

angrily        { printf("%s: is an adverb\n", yytext); }

to |

from |

behind |

above |

below |

between |

below          { printf("%s: is a preposition\n", yytext); }

if |

then |

and |

but |

or             { printf("%s: is a conjunction\n", yytext); }

their |

my |

your |

his |

her |

its            { printf("%s: is an adjective\n", yytext); }

I |

you |

he |

she |

we |

they           { printf("%s: in a pronoun\n", yytext); }

 

[a-zA-Z]+ {

         printf("%s:  don't recognize, might be a noun\n", yytext);

        }

.|\n           { ECHO; /* normal default anyway */ }

%%

main()

{

        yylex();

}

 

 

 

Symbol Tables

단어의 품사를 선언하고 입력되는 단어의 품사를 구분하기

definition section

%{

/*

 * Word recognizer with a symbol table.

 */

enum {

        LOOKUP = 0, /* default - looking rather than defining. */

        VERB, /* 동사 */

        ADJ,  /* 형용사 */

        ADV,  /* 부사  */

        NOUN, /* 명사 */

        PREP, /* 전치사 */

        PRON, /* 대명사 */

        CONJ  /* 접속사 */

};

int state;

int add_word(int type, char *word);

int lookup_word(char *word);

%}

 

 

rule section

%%

\n     { state = LOOKUP; }    /* end of line, return to default state */

^verb  { state = VERB; }

^adj   { state = ADJ; }

^adv   { state = ADV; }

^noun  { state = NOUN; }

^prep  { state = PREP; }

^pron  { state = PRON; }

^conj  { state = CONJ; }

[a-zA-Z]+  {

                /* a normal word, define it or look it up */

             if(state != LOOKUP) {

                /* define the current word */

                add_word(state, yytext);

             } else {

                switch(lookup_word(yytext)) {

                case VERB: printf("%s: verb\n", yytext); break;

                case ADJ: printf("%s: adjective\n", yytext); break;

                case ADV: printf("%s: adverb\n", yytext); break;

                case NOUN: printf("%s: noun\n", yytext); break;

                case PREP: printf("%s: preposition\n", yytext); break;

                case PRON: printf("%s: pronoun\n", yytext); break;

                case CONJ: printf("%s: conjunction\n", yytext); break;

                default:

                        printf("%s:  don't recognize\n", yytext);

                        break;

                }

            }

          }

.      /* ignore anything else */ ;

%%

 

 

user subroutine section

main()

{

        yylex();

}

/* define a linked list of words and types */

struct word {

        char *word_name;

        int word_type;

        struct word *next;

};

struct word *word_list; /* first element in word list */

extern void *malloc();

int

add_word(int type, char *word)

{

        struct word *wp;      

        if(lookup_word(word) != LOOKUP) {

                printf("!!! warning: word %s already defined \n", word);

                return 0;

        }

       

        /* word not there, allocate a new entry and link it on the list */

        wp = (struct word *) malloc(sizeof(struct word));

        wp->next = word_list;

        /* have to copy the word itself as well */

       

        wp->word_name = (char *) malloc(strlen(word)+1);

        strcpy(wp->word_name, word);

        wp->word_type = type;

        word_list = wp;

        return 1;      /* it worked */

}

int

lookup_word(char *word)

{

        struct word *wp = word_list;

        /* search down the list looking for the word */

        for(; wp; wp = wp->next) {

                if(strcmp(wp->word_name, word) == 0)

                        return wp->word_type;

        }

        return LOOKUP; /* not found */

}

실행 예

verb is am are were be being been do

is

is: verb

noun dog cat horse cow

verb chew eat lick

verb run stand sleep

dog run

dog: noun

run: verb

chew eat sleep cow horse

chew: verb

eat: verb

sleep: verb

cow: verb

horse: noun

verb talk

talk

talk: verb

 

 

문법(Grammars)

정해진 순서대로 토큰이 입력되는가? -- 문법 기술이 필요!

 

간단한 문장의 구성

noun verb.

noun verb noun.

 

문법을 기술하는 방식이 필요함

subject → noun | pronoun

object → noun

sentence → subject verb object

 

다양한 문장을 파싱하기 위하여는 문법을 확장하여야 함.

파서에서 어휘분석기(yylex)를 부르게하기 위하여 어휘분석기를 수정해야함.

 

 

파서(parser)와 렉서(lexer)간의 통신

파서가 상위의 루틴이되어야 함;- 파서(yyparse)는 yylex를 호출, yylex는 토큰(토큰 종류, 토큰 값)을 돌려줌. 따라서, 파서와 렉서는 같은 정의의 토큰을 가져야 함.

 

ex)우리의 품사 구분에서의 예

# define NOUN 257

# define PRONOUN 258

# define VERB 259

# define ADVERB 260

# define ADJECTIVE 261

# define PROPOSITION 263

# define CONJUCTION 263

 

yacc는 토큰정의를 위해 y.tab.h를 만듬.

 

new lexer

%{

/*

 * We now build a lexical analyzer to be used by a higher-level parser.

 */

#include "ch1-05y.h"  /* token codes from the parser */

#define LOOKUP 0 /* default - not a defined word type. */

int state;

%}

%%

\n     { state = LOOKUP; }

\.\n   {      state = LOOKUP;

                return 0; /* end of sentence */

        }

^verb  { state = VERB; }

^adj   { state = ADJECTIVE; }

^adv   { state = ADVERB; }

^noun  { state = NOUN; }

^prep  { state = PREPOSITION; }

^pron  { state = PRONOUN; }

^conj  { state = CONJUNCTION; }

[a-zA-Z]+ {

             if(state != LOOKUP) {

                add_word(state, yytext);

             } else {

                switch(lookup_word(yytext)) {

                case VERB:

                  return(VERB);

                case ADJECTIVE:

                  return(ADJECTIVE);

                case ADVERB:

                  return(ADVERB);

                case NOUN:

                  return(NOUN);

                case PREPOSITION:

                  return(PREPOSITION);

                case PRONOUN:

                  return(PRONOUN);

                case CONJUNCTION:

                  return(CONJUNCTION);

                default:

                  printf("%s:  don't recognize\n", yytext);

                  /* don't return, just ignore it */

                }

            }

          }

.      ;

%%

/* define a linked list of words and types */

struct word {

        char *word_name;

        int word_type;

        struct word *next;

};

struct word *word_list; /* first element in word list */

extern void *malloc();

int

add_word(int type, char *word)

{

        struct word *wp;      

        if(lookup_word(word) != LOOKUP) {

                printf("!!! warning: word %s already defined \n", word);

                return 0;

        }

       

        /* word not there, allocate a new entry and link it on the list */

        wp = (struct word *) malloc(sizeof(struct word));

        wp->next = word_list;

        /* have to copy the word itself as well */

       

        wp->word_name = (char *) malloc(strlen(word)+1);

        strcpy(wp->word_name, word);

        wp->word_type = type;

        word_list = wp;

        return 1;      /* it worked */

}

int

lookup_word(char *word)

{

        struct word *wp = word_list;

        /* search down the list looking for the word */

        for(; wp; wp = wp->next) {

                if(strcmp(wp->word_name, word) == 0)

                        return wp->word_type;

        }

        return LOOKUP; /* not found */

}

 

 

A Yacc Parser

다음은 yacc을 사용하는 첫 번째 예이다. lex의 입력과 유사하다.

%{

/*

 * A lexer for the basic grammar to use for recognizing english sentences.

 */

#include <stdio.h>

%}

%token NOUN PRONOUN VERB ADVERB ADJECTIVE PREPOSITION CONJUNCTION

%%

sentence: subject VERB object { printf("Sentence is valid.\n"); }

        ;

subject:       NOUN

        |      PRONOUN

        ;

object:        NOUN

        ;

%%

extern FILE *yyin;

main()

{

        while(!feof(yyin)) {

                yyparse();

        }

}

yyerror(s)

char *s;

{

    fprintf(stderr, "%s\n", s);

}

 

yacc입력의 구조

definition section

%%

rule section

%%

user subroutine section

 

The Rule Section

rule section은 실제 문법이 생성규칙(production rule)의 형식으로 기술되어야 한다. 각각의 생성규칙은 ":"를 중심으로 왼쪽에는 한 개의 이름이 오고, 오른 쪽에는 문법 심볼들의 나열과 행동코드, 그리고 세미콜론(";")으로 마감한다.

 

   rule section의 기술형식:

        이름 : 문법 심볼  { 행동(C코드) } ;

 

별도로 정하지 않으면, 첫 번째 로 기술된 규칙을 시작 규칙으로 한다.

   ex)

        statement:    NAME '=' expression

                |      expression            { printf("= %d\n", $1); }

                ;

        expression:  expression '+' expression { $$ = $1 + $3; }

                |      expression '-' expression { $$ = $1 - $3; }

                |      expression '*' expression { $$ = $1 * $3; }

                |      expression '/' expression

                                        {      if($3 == 0)

                                                        yyerror("divide by zero");

                                                else

                                                        $$ = $1 / $3;

                                        }

                |      '-' expression %prec UMINUS{ $$ = -$2; }

                |      '(' expression ')'  { $$ = $2; }

                |      NUMBER                { $$ = $1; }

                ;

 

   ex)

         sentence: subject VERB object    { printf("Sentence is valid.\n"); }

                ;

        subject:      NOUN

                |      PRONOUN

                ;

        object:               NOUN

 

 

user subroutine section

파서에 포함될 어떤 C 코드도 쓸수 있다.

   ex)

        extern FILE *yyin;

        main()

        {

                while(!feof(yyin)) {

                        yyparse();

                }

        }

        yyerror(s)

        char *s;

        {

            fprintf(stderr, "%s\n", s);

        }

 

 

좀더 복잡한 문장을 파싱하도록 yacc입력을 수정-ch1-06.y

%{

#include <stdio.h>

/* we found the following required for some yacc implementations. */

/* #define YYSTYPE int */

%}

%token NOUN PRONOUN VERB ADVERB ADJECTIVE PREPOSITION CONJUNCTION

%%

sentence: simple_sentence   { printf("Parsed a simple sentence.\n"); }

        | compound_sentence { printf("Parsed a compound sentence.\n"); }

        ;

simple_sentence: subject verb object

        |      subject verb object prep_phrase

        ;

compound_sentence: simple_sentence CONJUNCTION simple_sentence

        |      compound_sentence CONJUNCTION simple_sentence

        ;

subject:      NOUN

        |      PRONOUN

        |      ADJECTIVE subject

        ;

verb:          VERB

        |      ADVERB VERB

        |      verb VERB

        ;

       

object:               NOUN

        |      ADJECTIVE object

        ;

prep_phrase: PREPOSITION NOUN

        ;

%%

extern FILE *yyin;

main()

{

        while(!feof(yyin)) {

                yyparse();

        }

}

yyerror(s)

char *s;

{

    fprintf(stderr, "%s\n", s);

}

 

Running Lex and Yacc

% lex ch1-n.l

% yacc -d ch1-m.y

% cc -c lex.yy.c y.tab.c

% cc -o example-m.n lex.yy.o y.tab.o -ll -ly

 

 

Lex vs. Handwritten Lexers

(렉스로 스캐너를 자동생성하는 것과 직접 스캐너를 프로그램하는 것과의 비교)

 

hand coded lexical analyzer (Example 1-9. Sample C lexical analyzer)

  #include <stdio.h>

  #include <ctype.h>

  char *progname;

  #define NUMBER 400

  #define COMMENT 401

  #define TEXT 402

  #define COMMAND 403

  main(argc,argv)

  int argc;

  char *argv[];

  {

  int val;

  while(val = lexer()) printf("value is %d\n", val);

  }

 

  lexer()

  {

    int c;

    while ((c=getchar()) == ' ' || c == '\t')    ;

    if (c==EOF)

       return 0;

    if (c=='.' || isdigit(c))  {       /* number */

        while ((c=getchar()) != EOF && isdigit(c));

  if (c=='.') while ((c = gerchar()) != EOF && isdight(c));

        ungetc(c, stdin);

        return NUMBER;

    }

    if (c=='#')  {      /* comment */

       int index = 1;

       while ((c = getchar() != EOF && c != '\n');

       ungetc(c,stdin);

       return COMMENT;

    }

    if (c=='"')  {  /* literal text */

       int index = 1;

       while ((c = getchar()) != EOF &&

      c != '"' && c != '\n');

       if (c == '\n') ungetc(c, stdin);

       return TEXT;

    }

    if (isalpha(c))  {    /* check to see if it is a command */

       int index = 1;

       while((c = getchar()) != EOF && isalnum(c));

       ungetc(c, stdin);

       return COMMAND;

    }

    return c;

  }

 

Sample lex lexical analyzer

%{

  #define NUMBER   400

  #define COMMENT  401

  #define TEXT     402

  #define COMMAND  403

%}

%%

[ \t]+                   ;

[0-9]+                 |

[0-9]+\.[0-9]+         |

\.[0-9]+                 { return NUMBER;   }

#*                       { return COMMENT;   }

\"[^\"\n]*\"             { return TEXT;   }

[a-zA-Z][a-ZA-Z0-9]+     { return COMMAND;   }

\n                       { return '\n';   }

%%

#include <stdio.h>

 

main (argc, argv)

int argc;

char *argv[];

{

int val;

 

while(val = yylex()) printf("value is %d\n",val);

}

 

2. Using Lex(렉스 사용법)

 

Regular Expressions

패턴을 기술하기 위하여 패턴 연산은 메타 캐랙터(metacharacter)를 써서 표기

 

1) .   "\n"을 제외한 모든 글자를 매치시킴

 

2) *   이전의 정규식(regular expression)을 0번 이상 반복하여 매치시킴

 

3) []  character class를 표시: 기술된 글자중 하나를 매치시킴 []안에 기술된 메타캐랙터는 대부분 의미를 상실하나, "^", "-", "\"들은 특별한 의미를 가진다.

       만약 "^"(circumflex)가 첫글자로 나오면 다음의 글자들을 제외하고 매치시킴

        ex) [^\n]

            [^a-zA-Z]

 

       매치시킬 글자의 범위를 표시할 수 있다.

        ex) [0123456789]는 [0-9]로 표시할 수 있다.

 

       이스케이프 문자를 표시할 수 있다.

        ex) [ \t\n] 공백, 탭문자, 뉴라인 문자

            [\40-\176] 아스키 40인 공백부터 176인 "~"까지

 

 

4) ^   입력에서 라인의 첫 자로부터 매치시킨다.

        ex) ^#include       /* C의 전처리 명령 */

 

 

5) $   이전의 정규식을 라인의 끝에서만 매치한다.

        ex) hello$      /* 라인 끝의 hello를 매치한다 */

 

 

6) {}  이전의 정규식을 몇번 매치시킬 것인가를 표시한다.

        ex) ha{1,5}  /* ha, haa, haaa, haaaa, haaaaa를 매치시킨다 */

 

 

7) \   메타캐랙터를 이스케이프 문자로 만든다. C언어의 이스케이프 문자와 같다.

        ex) \n\t

            \*\+\$

 

 

8) +   이전의 정규식을 1번이상 반복하여 매치시킨다.

        ex) [0-9]+

 

 

9) ?   이전의 정규식을 0 또는 1번 매치시킨다.

        ex) -?[0-9]+

 

 

10) |    정규식들을 택일하여 매치시킨다. OR의 의미 이다.

        ex) - | \+

            case | CASE

 

 

11) "..." 리터럴로 표시되어 " "안의 모든 문자가 정규식으로 간주된다. 따라서 모든 메타캐랙터는 의미를 상실한다.

        ex) a"*"b      /* 토큰 a*b를 매치한다 */

 

 

12) /    이전의 정규식은 / 이후의 정규식이 매치될때만 매치된다.

        ex) hello/\n        /* 정규식 hello$와 같다 */

 

 

13) ()   괄호안의 정규식을 한 덩어리로 취급한다. 복잡한 정규식에 *, +, | 등의 연산을 하려할 때 유용하다.

        ex) (ha){1,3}  /* ha, haha, hahaha를 매치한다 */

 

 

정규식 기술의 예

[0-9]

[0-9]+

[0-9]*

-?[0-9]+

[0-9]*\.[0-9]+

([0-9]+)|([0-9]*\.[0-9]+)

-?([0-9]+)|([0-9]*\.[0-9]+)

[eE][-+}?[0-9]+

-?(([0-9]+)|([0-9]*\.[0-9]+)([eE][-+}?[0-9]+)?)

 

수치를 인식하는 렉스 스펙

%%

[\n\t ]       ;

-?(([0-9]+)|([0-9]*\.[0-9]+)([eE][-+]?[0-9]+)?) { printf("number\n"); }

.      ECHO;

%%

main()

{

        yylex();

}

 

라인 첫글자가 "#"이면 코멘트 시작

#.*

 

C의 스트링

\"[^"\n]*["\n]

\".*\"            /* "how" to "do"를 인식할까? */

\"[^"]*\"         /* \n이 나올 때까지 "이 나오지 않으면... */

 

 

단어세기

유닉스의 wc와 같은 기능을 가지는 단어세는 프로그램

 

definition section

%{

unsigned charCount = 0, wordCount = 0, lineCount = 0;

%}

word [^ \t\n]+

eol  \n

 

rule section

%%

{word}{ wordCount++; charCount += yyleng; }

{eol}  { charCount++; lineCount++; }

.      charCount++;

 

user subroutine section

%%

main(argc,argv)

int argc;

char **argv;

{

        if (argc > 1) {

                FILE *file;

                file = fopen(argv[1], "r");

                if (!file) {

                        fprintf(stderr,"could not open %s\n",argv[1]);

                        exit(1);

                }

                yyin = file;

        }

        yylex();

        printf("%d %d %d\n",charCount, wordCount, lineCount);

        return 0;

}

 

% ch2-02 ch2-02.l

467  72  30

 

Using Yacc

 

·         Writing a Yacc Specification

 문법 규칙 및 행동

symbol:     definition

            {action}

            ;

·         Yacc Spec의 형식

declarations

%%

grammar rules

%%

C programs

선언부 

%token         Declare the names of tokens.

%left          Definite left-associative operators.

%right         Define right-associative operators.

%nonassoc      Define operators that may not associate with themselves.

%type          Declare the type of nonterminals.

%union         Declare multiple data types for semantic values.

%start         Declare the start symbol. Default is first in rules section.

%prec          Assign precedence to a rule.

 

%{

C declarations

%}

) 정수 인식

$ cat print_int.y

%token INTEGER

%%

lines:      /* empty */

     | lines line

     { printf("= %d\n", $2);  }

     ;

line:   INTEGER   '\n'

     { $$ = $1; }

     ;

%%

#include "lex.yy.c"

$ lex print-int.l

$ yacc print-int.y

$ cc -o print-int y.tab.c -ly -ll

 

$ print-int

3

= 3

15

= 15

6

= 6

zippy

syntax error

$

A Specification for a Simple Adding Machine

%{

int sum_total = 0;

%}

%token INTEGER

%%

lines:   /* empty */

     | lines line

     ;

line:     '\n'

     |  exp '\n'

     { printf("= %d\n", sum_total); }

     ;

exp:  INTEGER            {sum_total += $1; }

    | '+' INTEGER           {sum_total += $2; }

    | '-' INTEGER           {sum_total -= $2; }

    | '=' INTEGER           {sum_total = $2; }

    | '='                   {sum_total = 0; }

    ;

%%

#include "lex.yy.c"

 

Writing the Lexical Analyzer

 

%%

[0-9]+    {

          sscanf(yytext, %d", &yylval);

          return (INTEGER);

          }

\n        return ('\n');

[-+=]     return yytext[0];

quit      return 0;

.         ;

 

 

Creating the Parser

 

$ lex addup.l

$ yacc addup.y

$ cc -o addup y.tab.c -ly -ll

 

$ addup

3

= 3

5

= 8

+4

= 12

-2

= 10

= 0

= 0

4

= 4

250

= 254

= 100

= 100

-50

= 50

quit

$

 

계산기 만들기(Building a Calculator)

 

계산기를 위한 인터프리터를 구성하여

    실질적인 계산기를 개발

 

   계산기는 인터프리터의 한 종류

     ex) 3 + 4 = 7

  

4칙 연산 기능은 필수

 

   어휘분석기(lexical analyzer): 입력 글자를 토큰 스트림으로

   ex)  36.7 + 43.2 입력

       REAL PLUS REAL 의 토큰 스트림 출력

 

   파서(parser): 적법한 수식으로 인식하기 위한 규칙을 가짐

 

      ex) rexpr REAL | rexpr '+' rexpr

 

   정의된 값을 반환

      ex) $$ = $1 + $3;

 

   expression 뒤의 new line을 인식할 규칙이 필요함

 

     ex) line '\n' | rexpr '\n'

 

 

Writing Regular Expressions for Tokens

 

   2 types of operands : integer & real number

 

   ex) valid real numbers

    3.1415926

       2.718281828

       6.02E28

 

   regular expression으로

     [0-9]+

 

([0-9]*"."[0-9]+) | ([0-9]*"."[0-9]+[eE][+-]?[0-9]+)

[0-9]*"."[0-9]+

[0-9]*"."[0-9]+[eE][+-]?[0-9]+

 

대치 스트링의 정의

형식:

name   translation

 

참조:

{name}

 

오퍼랜드 정의

integer    [0-9]+

dreal    ([0-9]*"."[0-9]+)

ereal    ([0-9]*"."[0-9]+[eE][+-]?[0-9]+)

real         {dreal} | {ereal}

n1           \n

 

 

Defining the Token Types

 

   token valueyylval을 통해 전달

   How to define different token type?

   ex) yylvaldouble

  %{

   #define YYSTYPE double

  %}

 

   ex) token value가 두가지 이상의 type가지기

   %union {

       double  real;       /*  real value  */

       int   integer;      /*  integer value  */

       }

 

   ex) yacc spec 밖에 정의

   typedef union  {

      double  real;       /*  real value  */

           int  integer;       /*  integer value  */

      }  YYSTYPE

 

   union member 알리기 :  < > 안에 표기

   ex)

   %token <real> REAL

     %token <integer> INTEGER

 

   nonterminal symboltype 알리기 : %type

   ex)

   %type <real> rexpr

   %type <integer> iexpr

 

   ex) yylvalmember 표시

    {

sscanf(yytext,"%lf", &yylval.real);

    return REAL;

      }

 

 

완성된 Lex Spec

%{

#include "y.tab.h"

%}

integer  [0-9]+

dreal    ([0-9]*"."[0-9]+)

ereal    ([0-9]*"."[0-9]+[eE][+-]?[0-9]+)

real     {dreal}|{ereal}

n1       \n

%%

[ \t]+    ;

integer  {sscanf(yytext, "%d", &yylval.integer);

            return INTEGER;

           }

real     {sscanf(yytext,"%lf", &yylval.real);

            return REAL;}

n1       {extern int lineno; lineno++;

            return '';

           }

.          {return yytext[0];}

%%

 

   header file을 생성시키기 위하여 yacc option으로 -d 사용하여야 함

 

 

Yacc Spec만들기

 

declaration section

%{

#include <stdio.h>

%}

 

%union  {

    double  real;      /* real value */

    int  integer;      /* integer value */

   }

 

%token <real> REAL

%token <integer> INTEGER

 

%type <real> rexpr

%type <integer> iexpr

 

%left '+' '-'    /* define associativity */

%left '*' '/'    /* define precedence, lowest to highest */

%left UMINUS

 

 

rule section

 

lines:  /* nothing */

| lines  line

;

line:  ‘\n’

| iexpr ‘\n’

   { printf(“%d\n”, $1);}

| rexpr ‘\n’

   { printf(“%15.8lf\n”, $1);}

| error ‘\n’

   {yyerror;}

;

iexpr: INTEGER

     | iexpr '+' iexpr

       { $$ = $1 + $3; }

     | iexpr '-' iexpr

        {$$ = $1 - $3; }

     | iexpr '*' iexpr

        {$$ = $1 * $3; }

     | iexpr '/' iexpr

       { if ($3) $$ = $1 / $3;

         else {

               fprintf(stderr,"divide by zero\n");

               yyerror;

              }

       }

     | '-' iexpr %prec UMINUS  /* tell yacc binds with      */

                                 /*  the specified precedence */

        {$$ = - $2; }

     | '(' iexpr ')'

        {$$ = $2; }

     ;

 

rexpr:  REAL

      | rexpr '+' rexpr

                 {$$ = $1 + $3; }

      | rexpr '-' rexpr

                 {$$ = $1 - $3; }

      | rexpr '*' rexpr

                 {$$ = $1 * $3; }

      | rexpr '/' rexpr

                 {if($3) $$ = $1 / $3;

                  else {

                        fprintf(stderr,"divide by zero\n");

                        yyerror;

                       }

                 }

       | '-' rexpr %prec UMINUS

                 {$$ = - $2; }

       | '(' rexpr ')'

                 {$$ = $2; }

       | iexpr '+' rexpr

                 {$$ = (double)$1 + $3; }

       | iexpr '-' rexpr

                 {$$ = (double)$1 - $3; }

       | iexpr '*' rexpr

                 {$$ = (double)$1 * $3; }

       | iexpr '/' rexpr

                 {if($3) $$ = (double)$1 / $3;

                  else {

                        fprintf(stderr,"divide by zero\n");

                        yyerror;

                       }

                 }

        | rexpr '+' iexpr

                  {$$ = $1 + (double)$3; }

        | rexpr '-' iexpr

                  {$$ = $1 - (double)$3; }

        | rexpr '*' iexpr

                  {$$ = $1 * (double)$3; }

        | rexpr '/' iexpr

                  {if($3) $$ = $1 / (double)$3;

                   else {

                         fprintf(stderr,"divide by zero\n");

                         yyerror;

                        }

                  }

         ;

code section

 

char *progname;

int lineno;

 

main(int argc, char **argv) {

   progname = argv[0];

  

   yyparse();

}

yyerror(char *s) {  /* print warning message  */

   fprintf(stderr, "%s: %s", progname, s);

   fprintf(stderr, "line %d\n", lineno);

}

 

 

Compilation

 

$ lex calc.l

$ yacc -d calc.y

$ cc -o calc y.tab.c lex.yy.c -ly -ll

 

 

Showing the Results

% calc

23 * 34   

782

14 + 5

19

12 * 23.3

   279.60000000

1 / 0

divide by zero

1

1 + 0

1

2.3 * 3.2

    7.36000000

3.14 * 45

  141.30000000

255 * 255

65025

255 * 255 + (3.2 * 4.3)

 65038.76000000

1024 * 1024

1048576

[출처] 6. LEX & YACC|작성자 에러

+ Recent posts