zzun.net

2007 Spring / SNU CSE / Prof. 이재진
Textbook - Compilers : Principles, Techniques and Tools 2/E by Aho, Lam, Sethi, Ullman (Pearson International Edition)

Chapter 2. A Simple Syntax-Directed Translator
This chapter is about the front end of a compiler : lexical analysis, parsing, intermediate code generation
Syntax-directed translator : infix arithmetic expressions into postfix expressions

2.1 Introduction
Three-address instruction : x = y op z (op:binary operator, x,y,z:addresses)

2.2 Syntax Definition
Context-free grammar (wikipedia)
ex) stmt → if ( expr ) stmt else stmt
  such a rule is called a production
  terminals : if else ( )
  nonterminals : stmt expr
  context-free : nonterminal → a sequence of terminals and/or nonterminals

2.2.5 Associativity of Operators
Left-associative : 9-5-2 : 5 belongs to the left - operator : (9-5)-2
Right-associative : a=b=c : b belongs to the rihgt = opertor : a=(b=c)

2.2.6 Precedence of Operators
Example grammar : * / have higher precedence than + -
expr → expr + term | expr - term | term
term → term * factor | term / factor | factor
factor → digit | ( expr )

2.3 Syntax-Directed Translation
Attributes : any quantity associated with a programming construct. : X.a (X:grammar symbol, a:attribute)
Translation Scheme : a notation for attaching program fragments to the productions of a grammar.

2.3.1 Postfix Notation
No parentheses are need in postfix notation.
ex) 952+-3*
1. find leftmost operator : +
2. its operands : 5 and 2 : 9(52+)-3* = 97-3*
3. next leftmost operator : -
4. its operands : 9 and 7 : (97-)3* = 23*
5. 23* = 6

2.3.2 Syntehsized Attributes
an attribute that its value at a parse-tree node N is determined from attribute values at the children of N and at N itself (bottom-up)
anotated parse tree : showing the attribute values at eache node

2.3.3 Simple Syntax-Directed Definitions
THE SAME ORDER concatenation of the translations of the nonterminals as in the production

2.3.5  Translations Schemes
semantic actions : program fragments : {print('+')}
need to perform a left-to-right depth-first postorder traversal

(to be continued)

Comment +0

100만달러 ‘수학난제’ 한국인이 풀었다

[한겨레 2004-12-05 20:51]  


[한겨레] 현상금 100만달러가 걸린 세계 7대 수학난제 중 첫번째 문제를 김양곤(55·수학통계정보과학부) 전북대 교수가 이끄는 국내 연구팀이 3년 만에 풀어냈다.
김 교수는 5일 “미국 클레이 수학재단(CMI)이 지난 2000년 상금 700만달러를 걸고 발표했던 세계 7대 난제 중 1번 문제를 풀어 독일의 논문평가기관인 첸트랄블라트에서 발간하는 논문집에 수록했다”고 밝혔다.

김 교수는 미국 위스콘신 대학 남기봉 교수와 함께 1번 문제인 ‘P 대 NP’를 공동으로 해결했다. 이번 논문은 지난 3월에 인도의 한 저널에도 발표됐다. 김 교수가 푼 ‘P 대 NP’는 컴퓨터 알고리즘과 관련된 분야로 수학의 귀납법 풀이는 가능하나 연역적 풀이도 가능한가라는 문제로 물리학자들도 향후 10~20년 이후 해답이 나올 것으로 예측했다. 김 교수의 논문은 게재 후 2년 동안 수학계의 반응을 본 뒤 클레이 수학재단의 심사를 거쳐 100만달러를 수상하게 된다.

전주/박임근 기자 pik007@hani.co.kr ⓒ 한겨레(http://www.hani.co.kr), 무단전재 및 재배포 금지

Comment +4

  • zzun 2004.12.06 08:35 신고

    알고리즘 시간에 많이 들은 얘기지만..
    P=NP 가 연역적으로 풀이 가능하다면 정말
    알고리즘 학계에 역사상 최대의 사건이 되는건데 -_-
    그동안 수많은 시도가 있었고 다들 '풀었다!'라고 했지만
    다른 수학자 혹은 공학자들이 항상 오류를 발견해내었다 ㅡㅡ;;

    왠지 이번에도 그럴것 같은 느낌...

  • 2004.12.06 16:30 신고

    문병로 교수님이 수엽시간에 한이야기 생각난다
    그 수업들을 당시 약 몇초간...생각한건데..
    '함 풀어보까?'
    ㅋㅋㅋ

  • 2004.12.06 23:05 신고

    허허..전에 assignment problem 풀 때, 잠시 본 문제였는데..
    문제 자체를 이해하기도 힘들던데.. 허허..

  • zzun 2004.12.06 23:32 신고

    뵨//나도 그때 몇초간 생각했었어 ㅋㅋ
    엽//알고리즘 수업 들으면 문교수님이 친절히 설명해주신다 -_-;

[info.]
2004 여름 / 네트워크 프로그래밍(경북대) / 고석주 교수님
using : C / Linux / TCP/IP / Multi-threads / thread-synchronization(mutex)


[Makefile]
all : zchat_serv zchat_clnt

zchat_serv : zchat_serv.c zchat.h
       gcc -o zchat_serv zchat_serv.c -D_REENTRANT -lpthread

zchat_clnt : zchat_clnt.c zchat.h
       gcc -o zchat_clnt zchat_clnt.c -D_REENTRANT -lpthread


[zchat.h]
/**

Z-Chat Header File

zzun
hello82@unitel.co.kr
http://zzun.net

**/

#include <stdio.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <pthread.h>
#include <string.h>

#define BUFSIZE 100
#define IDSIZE 20
#define CLNT_LIMIT 10


[zchat_serv.c]
/**

Z-Chat SERVER

zzun
hello82@unitel.co.kr
http://zzun.net

**/

#include "zchat.h"

struct clnt_info
{
       int sock;
       char* id;
};

int clnt_count = 0;
struct clnt_info* clients[CLNT_LIMIT];
pthread_mutex_t mutx;

void error_handler( char* msg )
{
       fputs( msg, stderr );
       fputc( '\n', stderr );
       exit(1);
}

void sendtoall_ex( char* msg, int sender, int len )                // send to all except sender
{
       int i;
       char id_msg[BUFSIZE+IDSIZE+3];
       
       pthread_mutex_lock( &mutx );
       for ( i=0; i<clnt_count; i++ )
               if ( clients[i]->sock == sender )
               {
                       sprintf( id_msg, "[%s] %s", clients[i]->id, msg );        // attach sender's id
                       len += strlen(clients[i]->id) + 3;
                       break;
               }
       for ( i=0; i<clnt_count; i++ )
               if ( clients[i]->sock != sender )
                       write( clients[i]->sock, id_msg, len );
       pthread_mutex_unlock( &mutx );
}

void sendtoone( char* msg, int sender, int len )        // usage : /id msg
{
       int i, target_sock, id_len;
       char id_msg[BUFSIZE+IDSIZE+15];
       char target_id[IDSIZE];

       id_len = strchr(msg, ' ') - msg - 1;
       strncpy( target_id, msg+1, id_len );
       target_id[id_len] = 0;
       msg = msg + id_len + 2;                // detach target id

       pthread_mutex_lock( &mutx );
       for ( i=0; i<clnt_count; i++ )
       {
               if ( clients[i]->sock == sender )        // attach sender's id
               {
                       sprintf( id_msg, "[Secret from:%s] %s", clients[i]->id, msg );
                       len += strlen(clients[i]->id) + 15;
               }
               if ( !strcmp(target_id, clients[i]->id) )
                       target_sock = clients[i]->sock;
       }        
       pthread_mutex_unlock( &mutx );

       write( target_sock, id_msg, len );
}

void* clnt_msg_process(void* arg)
{
       int clnt_sock = (int) arg;
       char msg[BUFSIZE];
       int i, len;

       while ( (len=read(clnt_sock, msg, sizeof(msg))) != 0 )
       {
               if ( msg[0] == '/' )
                       sendtoone( msg, clnt_sock, len );        // whisper
               else
                       sendtoall_ex( msg, clnt_sock, len );
       }

       pthread_mutex_lock( &mutx );
       for ( i=0; i<clnt_count; i++)
               if ( clnt_sock == clients[i]->sock )
               {
                       printf( "%s's connection closed.\n", clients[i]->id );
                       free( clients[i]->id );
                       free( clients[i] );
                       for ( ; i<clnt_count-1; i++)
                               clients[i] = clients[i+1];                        
                       break;
               }
       clnt_count--;
       pthread_mutex_unlock( &mutx );        

       close( clnt_sock );
       return 0;
}

int main( int argc, char** argv )
{
       int serv_sock, clnt_sock;
       struct sockaddr_in serv_addr;
       struct sockaddr_in clnt_addr;
       int clnt_addr_size;
       pthread_t thread;

       if ( argc != 2 )
       {
               printf( "Usage : %s <port>\n", argv[0] );
               exit(1);
       }

       if ( pthread_mutex_init(&mutx, NULL) )
               error_handler( "pthread_mutex_init() error" );

       serv_sock = socket( PF_INET, SOCK_STREAM, 0 );

       memset( &serv_addr, 0, sizeof(serv_addr) );
       serv_addr.sin_family = AF_INET;
       serv_addr.sin_addr.s_addr = htonl( INADDR_ANY );
       serv_addr.sin_port = htons( atoi(argv[1]) );

       if ( bind(serv_sock, (struct sockaddr*) &serv_addr, sizeof(serv_addr)) )
               error_handler( "bind() error" );

       if ( listen(serv_sock, CLNT_LIMIT) )
               error_handler( "listen() error" );

       while (1)
       {
               clnt_addr_size = sizeof(clnt_addr);
               clnt_sock = accept( serv_sock, (struct sockaddr*) &clnt_addr, &clnt_addr_size );

               pthread_mutex_lock( &mutx );
               clients[clnt_count] = (struct clnt_info*) malloc( sizeof(struct clnt_info) );
               clients[clnt_count]->id = (char*) malloc( IDSIZE );
               clients[clnt_count]->sock = clnt_sock;
               read( clnt_sock, clients[clnt_count++]->id, IDSIZE );        // recv clnt's id
               pthread_mutex_unlock( &mutx );

               pthread_create( &thread, NULL, clnt_msg_process, (void*)clnt_sock );
               printf( "new client connected : %s\n", clients[clnt_count-1]->id );
       }

       return 0;
}


[zchat_clnt.c]
/**

Z-Chat CLIENT

zzun
hello82@unitel.co.kr
http://zzun.net

**/

#include "zchat.h"

void error_handler( char* err_msg )
{
       fputs( err_msg, stderr );
       fputc( '\n', stderr );
       exit(1);
}

void* send_msg( void* arg )
{
       char msg[BUFSIZE];

       int sock = (int) arg;        
       while (1)
       {
               fgets( msg, BUFSIZE, stdin );
               if ( !strcmp(msg, "q\n") )
               {
                       close( sock );
                       exit(0);
               }
               write( sock, msg, strlen(msg) );
       }
}

void* recv_msg( void* arg )
{
       int sock = (int) arg;
       char recieved[BUFSIZE+IDSIZE+15];
       int len;

       while (1)
       {
               len = read( sock, recieved, BUFSIZE+IDSIZE+14 );
               if ( len == -1 )
                       return (void*)1;
               recieved[len] = 0;
               fputs( recieved, stdout );
       }
}

int main( int argc, char** argv )
{
       int sock;
       struct sockaddr_in serv_addr;
       pthread_t send_thrd, recv_thrd;
       void* thr_rtn_val;
       char id[IDSIZE];

       if ( argc != 4 )
       {
               printf( "Usage : %s <IP> <port> <ID>\n", argv[0] );
               exit(1);
       }

       sprintf( id, "%s", argv[3] );

       sock = socket( PF_INET, SOCK_STREAM, 0 );
       if ( sock == -1 )
               error_handler( "socket() error" );

       memset( &serv_addr, 0, sizeof(serv_addr) );
       serv_addr.sin_family = AF_INET;
       serv_addr.sin_addr.s_addr = inet_addr( argv[1] );
       serv_addr.sin_port = htons( atoi(argv[2]) );

       if ( connect(sock, (struct sockaddr*) &serv_addr, sizeof(serv_addr)) == -1 )
               error_handler( "connect() error" );

       write( sock, id, sizeof(id) );        // send my id

       pthread_create( &send_thrd, NULL, send_msg, (void*) sock );
       pthread_create( &recv_thrd, NULL, recv_msg, (void*) sock );

       pthread_join( send_thrd, &thr_rtn_val );
       pthread_join( recv_thrd, &thr_rtn_val );        // wait until threads die

       close( sock );
       return 0;
}

'IT > 소스코드' 카테고리의 다른 글

[C/linux] Z-Chat (TCP/IP Chat Program)  (0) 2004.07.12
[C/linux] TCP/IP 가위바위보 게임 (Concurrent Server Version)  (0) 2004.07.07
Intersecting Circles  (2) 2004.06.15
[C++] Orchard Trees  (0) 2004.06.04
[C++] Maximum Sum (upgrade)  (2) 2004.05.18
[C++] Maximum Sum  (0) 2004.05.10

Comment +0


티스토리 툴바