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 value는 yylval을 통해 전달

   How to define different token type?

   ex) yylval을 double로

  %{

   #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 symbol의 type 알리기 : %type

   ex)

   %type <real> rexpr

   %type <integer> iexpr

 

   ex) yylval의 member 표시

    {

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

main.cpp
#include "a.h"
int main(void)
{
     a_func();
}

a.cpp
#include <stdio.h>
void a_func(void)
{
    printf("hello world\n");
}

a.h
extern void a_func(void);

///--> 주의 extern "C"를 사용하지 않는다. main.cpp , a.cpp 모두 같은 cpp 파일이다.

----------------------
gcc -c -o test.out a.cpp main.cpp 를 하면 다음과 같은 에러가 발생한다.

/tmp/ccSBYZq4.o(.eh_frame+0x11): undefined reference to `__gxx_personality_v0'

gcc는 c,와 c++에 대해서 유연하게 대응하지 못한다, 특히 C++에 대해서
따라서, 명시적으로 g++을 이용하거나 libstdc++을 추가하는 방법으로 해야한다.

g++ -c -o test.out a.cpp main.cpp
gcc -c -o test.out a.cpp main.cpp -lstdc++

<주의 .. -Lstdc++ 안됨. L의 소문자  이어야 한다.>

Epoll은 기존 select 모델의 한계를 뛰어넘는 새로운 스타일의 서버입니다.

기존 select의 경우 일정 비트열을 두고 그곳에 0 이냐 1이냐로 클라이언트의 응답을 기다리는 방식이라 약 300~500 클라이언트 이상 동접시 속도저하 문제가 나타난다고 합니다.

(이 말은 즉, 동접 300 가량 정도는 select 으로 써도 상관은 없다는 얘기죠;;)
 

그래서 이를 해결하기 위해 아예 하드웨어적으로 클라이언트의 접속 변화를 감지해서 recv냐 send냐 를 판별해 주는 함수가 epoll 이라 합니다.

 

문제는 이게.. 리눅스에서 만든거라 윈도우에선 사용이 불가능합니다.

그리고 리눅스도 커널 2.6 이상에서만 된다고 합니다.

 

하여간 소스 들어갑니다.

소스가.. 일단 숙제용으로서.. 게임서버 시간의 숙제를 하다가 이것저것 조사하고 찾은걸
(인터넷과 man 메뉴얼)로 짜집기 한겁니다.. orz
 

chatServer.c

#include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <string.h> #include <sys/epoll.h>                     // 이게 중요 #include <arpa/inet.h> #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <netinet/tcp.h> #include <fcntl.h> #include <sys/ioctl.h> #include <errno.h>   #define EPOLL_SIZE 60 #define EPOLL_EVENT_SIZE 100 #define OPENPORT 9000                       // open port 번호 // main int main (int argc, char **argv) {         struct epoll_event *events;          // epoll 관련         struct epoll_event ev;                 struct sockaddr_in addr, clientaddr;         int clilen;         int sfd, efd, cfd;                   // server 소켓, epoll 소켓, client 소켓         int i,j;                             // for문을 위해         int max_got_events;         int result;         int readn;         int sendflags = 0;         char buf_in[256] = { '\0' };         // 버퍼         int count = 0;           // epoll 소켓 생성         if ((efd = epoll_create (EPOLL_EVENT_SIZE)) < 0)         {                 perror ("epoll_create (1) error");                 return -1;         }           // init pool         events = (struct epoll_event *) malloc (sizeof (*events) * EPOLL_SIZE);         if (NULL == events)         {                 perror ("epoll_create (0) error");                 return -1;         }           // 서버 소켓 생성         clilen = sizeof (clientaddr);         sfd = socket (AF_INET, SOCK_STREAM, 0);         if (sfd == -1)         {                 perror ("socket error :");                 close (sfd);                 return -1;         }         // 소켓 정보 넣고 bind, listen 처리          addr.sin_family = AF_INET;         addr.sin_port = htons (OPENPORT);         addr.sin_addr.s_addr = htonl (INADDR_ANY);         if (bind (sfd, (struct sockaddr *) &addr, sizeof (addr)) == -1)         {                 close (sfd);                 return -2;         }         listen (sfd, 5);           if (sfd < 0)         {                 perror ("init_acceptsock error");                 return 1;         }         // 서버시작, epoll 이벤트 설정 및 컨트롤 함수로 활성화          printf("Running Server port %d\n",OPENPORT);         ev.events = EPOLLIN;         ev.data.fd = sfd;         result = epoll_ctl (efd, EPOLL_CTL_ADD, sfd, &ev);         if (result < 0)         {                 perror ("epoll_ctl error");                 return 1;         }           // 서버 실제 루트         while (1)         {                 // epoll 이벤트 대기 (클라이언트의 반응(접속 or send) 감지)                 max_got_events = epoll_wait (efd, events, EPOLL_SIZE, -1);                               // epoll 이벤트 받은만큼의 숫자만큼 for                 for (i = 0; i < max_got_events; i++)                 {                         // 이벤트 들어온 소켓이 연결 요청이면                         if (events[i].data.fd == sfd)                         {                                 cfd = accept (sfd, (struct sockaddr *)                                                 &clientaddr, &clilen);                                 if (cfd < 0)                                 {                                         perror ("Accept error");                                         return -1;                                 }                                   ev.events = EPOLLIN;                                 ev.data.fd = cfd;                                 epoll_ctl (efd, EPOLL_CTL_ADD, cfd, &ev);                                   printf("Accepted socket : %d\n",cfd);                                 count++;                         }                         // 그게 아니면,                         else                         {                                 cfd = events[i].data.fd;                                   memset (buf_in, 0x00, 256);                                 readn = read (cfd, buf_in, 255);                                 // if it occured ploblems with reading,                                 // delete from epoll event pool and close socket                                                                                                                        // readn 값이 0 이하이면 recv 처리                                 if (readn <= 0)                                 {                                         epoll_ctl(efd, EPOLL_CTL_DEL, cfd, &ev);                                         close (cfd);                                         printf ("Close fd %d\n", cfd);                                           count--;                                 }                                 else                                 {                                 // 아니면 send 처리                                 //      printf ("%s", buf_in);                                         for(j=5; j<count+5; j++)                                         {                                           // 단 이벤트로온 client엔 send 하지말고                                           // 다른 모든 클라이언트에 send 해서 채팅                                                 if(cfd != j)                                                         send (j, buf_in,                                                          strlen (buf_in),                                                          sendflags);                                         }                                 }                           }                 }         }         return 1; }

 

맨 아래쪽의

For j=5 라고 했는데, 리눅스에선 소켓 번호가 윈도우와 달리 5번부터인가 시작되서 그렇습니다.

윈도우는 OS가 자기 맘대로 할당하지만 리눅스에선 0~4번이 정해져 있고 그 이후 차례대로 count 됩니다..
물론 저 소스는 야메로 짠거라 문제 발생 요지가 많습니다. Orz

 

참고로 클라이언트는…

그냥 telnet으로 telnet 127.0.0.1 9000 으로 접속하면 됩니다.

아래 소스는 인터넷에 떠돌고 있는 리눅스용 select 서버를 가져와서 윈도우 용으로 수정하였습니다.

출처는 : http://vessel.tistory.com/95 입니다.

 

리눅스에선 서버만 만들어 놓고 클라이언트는 telnet으로 접속이 가능합니다만.

저는 이걸 윈도우 용으로 전환하면서 클라이언트 프로그램도 그냥 만들었습니다… orz

윈도우도 telnet 이 있긴하지만.. 이건 좀…

 

하여간 소스 들어갑니다.

 

Server.cpp

#include <winsock2.h> #include <stdlib.h> #include <stdio.h> #include <string.h>   #define MAXLINE 512 #define MAX_SOCK 64 char *escapechar = "exit"; int maxfdp1; int num_chat = 0;                                                                               // 채팅참가자수 int client_s[MAX_SOCK];   // 채팅탈퇴처리 void removeClient(int)                              // i번째참가자탈퇴 {         closesocket(client_s[i]);                   // 해당소켓닫기         if(i !=num_chat -1)                client_s[i] = client_s[num_chat -1];          num_chat --;                                // 채팅참가자수1명줄이기         printf("채팅참가자1명탈퇴. 현재참가자수= %d\n",num_chat); }   // client_s[]내의최대소켓번호얻기(k는초기치) int getmax(int k) {         int max = k;         int r;         for(r = 0; r < num_chat ; r++)            // 채팅참가자수만큼소켓배열탐색                if(client_s[r] > max)                        max = client_s[r];         return max; }   int main() {         char rline[MAXLINE], my_msg[MAXLINE];               // buffer 생성         char *start = "Connetctd to chat_server\n";         // 최초연결시보내는메세지         int i,j,n;         SOCKET s, client_fd, clilen;         fd_set read_fds;         struct sockaddr_in client_addr, server_addr;        // 소켓주소구조체선언         WSADATA wsa;                                        // 윈소켓           // 윈속초기화         if(WSAStartup(MAKEWORD(2,2), &wsa) != 0)                exit(1);           // 초기소켓생성         if((s = socket(AF_INET, SOCK_STREAM, 0)) < 0)         {                printf("Server: Can't open stream socket.");                exit(0);         }         // server_addr 구조체의내용세팅         ZeroMemory(&server_addr, sizeof(server_addr));       //초기화(0으로채운다)         server_addr.sin_family = AF_INET;         server_addr.sin_addr.s_addr = htonl(INADDR_ANY);         server_addr.sin_port = htons(9000);                   // bind()         if(bind(s,(struct sockaddr *)&server_addr,sizeof(server_addr)) < 0 )              {                printf("Server: Can't bind local address.\n");                exit(0);         }           //클라이언트로부터연결요청을기다림         listen(s,SOMAXCONN);                    // listen 접속대기(큐크기5)         maxfdp1 = s + 1;                        // 최대소켓번호+1         while(1)         {                FD_ZERO(&read_fds);              // fd_set  초기화(0으로세팅)                 FD_SET(s,&read_fds);       // 소켓에해당하는file discripter를1로세팅                for(i=0; i<num_chat; i++)        // ""                        FD_SET(client_s[i], &read_fds);                maxfdp1 = getmax(s) +1;         // maxfdp1 재계산                  if(select(maxfdp1,&read_fds, (fd_set  *)0, (fd_set *) 0, (struct timeval *) 0) < 0)     // select setting                {                        printf("select error =< 0 \n");                        exit(0);                }                if(FD_ISSET(s, &read_fds))  // read_fds 중s에해당하는비트가세팅되있다면                {                                      int addrlen;        // 의미없음ㅡㅡ.. 단순주소길이저장변수                        addrlen = sizeof(client_addr);                                               // == 연결요청이있다면                        clilen = sizeof(client_addr);                        client_fd = accept(s, (struct sockaddr *)&client_addr, &addrlen);                                          //  accept()                        if(client_fd == -1)                        {                               printf("accept error \n");                               exit(0);                        }                          // 채팅클라이언트목록에추가                        client_s[num_chat] = client_fd;                        num_chat++;                       // 채팅참가자수1 증가                         // "Connetctd to chat_server" 를접속한클라이언트에보냄                                            send(client_fd,start,strlen(start),0);                             printf("%d번째사용자추가,\n",num_chat);                }                  //클라이언트가보낸메시지를모든클라이언트에게방송                for(i = 0; i<num_chat; i++)              // 모든클라이언트검색                {                        memset(rline,'\0',MAXLINE);      // buffer 초기화                        if(FD_ISSET(client_s[i],&read_fds))                        // read 해당소켓에서read 할것이있는지확인                        {                               if((n = recv(client_s[i],rline,MAXLINE, 0 )) <= 0)                               {                                       removeClient(i);                                       continue;                               }                               // 종료문자처리                               if(strstr(rline,escapechar) != NULL)                               //"exit"가입력되면종료시키기                               {                                       removeClient(i);                                       continue;                               }                               // 모든채팅참가자에게메시지방송                               rline[n] = '\0';                               for(j = 0; j < num_chat; j++)                                       send(client_s[j],rline,n,0);                               printf("%s\n",rline);                        }                }         }         closesocket(s);                                                                                                                                                        // closesocket()         WSACleanup();                                                                                                                                                  // 윈속종료         return 0; }

 

아래는 클라이언트 소스입니다.

Client.cpp

/***********************************************         스레드를사용한채팅클라이언트    원래루트는recv 전용이고    스레드를생성해서사용자입력대기하다가,    입력받게되면send 해주는클라이언트임. ***********************************************/   #include <winsock2.h> #include <stdlib.h> #include <stdio.h> #include <string.h>   #define MAXLINE     512   DWORD WINAPI ProcessInputSend(LPVOID arg);   char *escapechar = "exit"; char name[10]; // 채팅에서사용할이름 char line[MAXLINE], message[MAXLINE+1]; struct    sockaddr_in   server_addr; SOCKET s;      // 서버와연결된소켓번호   int main() {         WSADATA wsa;                          // 윈속           // 채팅참가자이름구조체초기화         printf("채팅ID 입력: ");         scanf("%s",name);                 // 윈속초기화         if(WSAStartup(MAKEWORD(2,2), &wsa) != 0)                exit(1);           // 소켓생성         if ((s = socket(AF_INET, SOCK_STREAM, 0)) < 0)         {                printf("Client : Can't open stream socket.\n");                exit(0);         }           // 채팅서버의소켓주소구조체server_addr 초기화         ZeroMemory(&server_addr, sizeof(server_addr));         server_addr.sin_family = AF_INET;         server_addr.sin_port = htons(9000);         server_addr.sin_addr.s_addr = inet_addr("127.0.0.1");                 // 연결요청         if(connect(s, (struct sockaddr *)&server_addr, sizeof(server_addr)) < 0)         {                printf("Client : Can't connect to server.\n");                exit(0);         }         else         {                printf("서버에접속되었습니다. \n");         }           // 스레드생성         HANDLE hThread;         DWORD ThreadId;         hThread = CreateThread(NULL, 0, ProcessInputSend, 0, 0, &ThreadId);         if(hThread == NULL)                printf("[오류] 스레드생성실패!\n");         else                CloseHandle(hThread);           while(1)         {                ZeroMemory(message, sizeof(message));                int size;                if((size = recv(s, message, MAXLINE, 0)) == SOCKET_ERROR)                {                        printf("recv()");                        exit(0);                }                else                {                        message[size] = '\0';                        printf("%s \n", message);                }         }         closesocket(s);                       // closesocket()         WSACleanup();                 // 윈속종료 }     // 사용자입력부분 DWORD WINAPI ProcessInputSend(LPVOID arg) {         while(true)         {                if(fgets(message, MAXLINE, stdin))                {                        sprintf(line, "[%s] %s", name, message);                        if (send(s, line, strlen(line), 0) < 0)                               printf("Error : Write error on socket.\n");                        if (strstr(message, escapechar) != NULL )                        {                               printf("Good bye.\n");                               closesocket(s);                               exit(0);                        }                }         }         return 0; }

 

아래의 클래스를 사용해서 뻘짓을 하는 쓰레드 서버보단 이쪽이 훨씬 직관적이지 않습니까?

>_<..

여튼 이것도 좀 여러군데 손을 봐야 하긴 하지만..

이걸로 간단한 채팅이 되는 소스입니다.

 

클라이언트에서 쓰레드를 나눈이유는
recv처리와 send 처리를 동시에 하기 위해서 랍니다. 쓰레드를 나눔으로서
윈도우 프로그램으로 보면, 언제던지 server로부터 메시지를 받을수 있는 recv 프로세서와
언제던지 사용자가 키보드 입력을 받을수 있는 send 프로세서가 동시에 실행이 되는셈이죠

자세한 설명은.. 네트워크 프로그래밍 책의 대부분 뒷부분에 있는 select 설명을 보시는게 낳으실껍니다 >_<;;