계산기: 귀속 하강법 구조, 표지부 지원

44959 단어 계산기
문법, BNF로 표시
   ->
{ (+|-) }
   ->
{ (*|/) }
 ->
()
| num
| indent
| indent =
num
십진 실수 표시
indent
식별자를 나타냅니다.식별자는 문자와 숫자로 구성된 시퀀스이며 첫 번째 문자는 문자여야 합니다.
또한 Expr는';'결말
문법 분석 트리의 특징에 따라 저층에 있는 선구값, 즉 우선순위가 높다는 것이다.
문법에서 알 수 있듯이 *,/우선순위가 가장 높음;+,-그 다음;부치 조작부호 = 가장 낮고, 또한 부치 조작부호는 오른쪽 결합성을 가지고 있다. 예를 들어 a=b=c;a=(b=c)와 같다.(이것들은 모두 문법에 포함된 것이지 약속이 아니다)
1. 어법 분석
Token 종류: 실수, 식별자, 연산자, 구분자.

      
        
enum token_type{
NUMBER, IDENT, OPERATOR, SEPARATOR, UNKOWN
};
   

 
Token 구조

      
        
struct Token{
int type;
union{
double val; //
char * name; //
int op; // 、 ,
}u;
};

 
hash 메모리 식별자 사용하기
HashNode 구조

      
        
// hash, ,
struct HashNode{
char * name;
double value;
struct HashNode * next;
};
typedef
struct HashNode HashNode;

문자열hash 함수

      
        
int hash( char * s)
{
int hashval;
for (hashval = 0 ; * s != ' \0 ' ; ++ s)
hashval
= * s + 31 * hashval;
if (hashval < 0 )
hashval
= - hashval;
return hashval % HASHSIZE;
}

lookup(char*name) 검색 저장소name의 HashNode

      
        
HashNode * lookup( char * name)
{
int hash_value = hash(name);
HashNode
* ptr;
ptr
= hash_table[hash_value];
for (; ptr != NULL; ptr = ptr -> next)
if (strcmp(ptr -> name, name) == 0 )
return ptr;

//
ptr = (HashNode * )malloc( sizeof (HashNode));
ptr
-> name = ( char * )malloc(strlen(name) * sizeof ( char ) + 1 );
strcpy(ptr
-> name, name);
ptr
-> value = 0 ;

ptr
-> next = hash_table[hash_value];
hash_table[hash_value]
= ptr;

return ptr;
}

 
구문 분석 프로그램:

       
         
struct Token next_token;
//
void lex(){
int c;
while ((c = getchar()) != EOF && isspace(c))
;
if (isdigit(c)){ //
next_token.type = NUMBER;
next_token.u.val
= get_num(c);
return ;
}
else if (isalpha(c)){ //
char * name = get_ident(c);
name
= lookup(name) -> name;
next_token.type
= IDENT;
next_token.u.name
= name;
return ;
}
//
next_token.u.op = c;
switch (c){
case ' + ' :
case ' - ' :
case ' * ' :
case ' / ' :
case ' = ' :
next_token.type
= OPERATOR;
break ;
case ' ( ' :
case ' ) ' :
case ' ; ' :
next_token.type
= SEPARATOR;
break ;
default :
next_token.type
= UNKOWN;
}
}

double get_num( char c){
int val;
val
= c - ' 0 ' ;
while (isdigit(c = getchar()))
val
= val * 10 + c - ' 0 ' ;
int n = 0 ;
if (c == ' . ' ){
while (isdigit(c = getchar())){
n
++ ;
val
= val * 10 + c - ' 0 ' ;
}
}
ungetc(c, stdin);
return (val / pow( 10 , n));
}

#define BUFSIZE 100
char * get_ident( char c){
static char buf[BUFSIZE];
int bufp = 0 ;

buf[bufp
++ ] = c;
while (isalnum(c = getchar()))
buf[bufp
++ ] = c;
ungetc(c, stdin);
buf[bufp]
= ' \0 ' ;
return buf;
}

  
2. 문법 분석
귀속 하강 서브루틴을 작성하는 협정은 다음과 같다.
모든 하위 프로그램은 전역량nextToken에 다음 입력한 token을 넣습니다.
따라서 문법 분석 함수를 시작할 때nextToken은 아직 문법 분석 과정에 사용되지 않은 입력 표기 중 가장 왼쪽에 있는 표기를 가지고 있다고 가정한다.
또 다른 해결 방안은 모든 귀속 서브루틴이 자동으로 다음 표시를 취하고 처리할 수 없으면 되돌려 놓는 것이다.우리는 전종의solution을 채택한다.
세 개의 비종결자는 세 개의 귀속 서브루틴에 대응한다.
표현식:

       
         
// <expr> -> <term> { (+ | -) <term> }
double expr()
{
double val;

// term
val = term();

// token + - ,
// lex() token,
// term
while (next_token.type == OPERATOR &&
(next_token.u.op
== ' + ' || next_token.u.op == ' - ' )){
int op = next_token.u.op;
lex();

if (op == ' + ' )
val
+= term();
else if (op == ' - ' )
val
-= term();
}
return val;
}

항목:

       
         
// <term> -> <factor> { (* | /) <factor> }
double term()
{
double val;

// factor
val = factor();

// token * / ,
// lex() token,
// factor
while (next_token.type == OPERATOR &&
(next_token.u.op
== ' * ' || next_token.u.op == ' / ' )){
int op = next_token.u.op;
lex();

if (op == ' * ' ){
val
*= factor();
}
else if (op == ' / ' ){
int tmp;
tmp
= factor();
if (fabs(tmp) < 1e - 6 ){
fprintf(stderr,
" 0 " );
exit(
1 );
}
else {
val
/= tmp;
}
}
}
return val;
}

인자:

       
         
// <factor> -> (<expr>) | num | ident | ident = <expr>
double factor(){
double val;
if (next_token.type == SEPARATOR && next_token.u.op == ' ( ' ){
lex();
val
= expr();
if (next_token.type == SEPARATOR && next_token.u.op == ' ) ' ){
lex();
// token
} else {
fprintf(stderr,
"
" );
exit(
1 );
}
}
else if (next_token.type == NUMBER){
val
= next_token.u.val;
lex();
}
else if (next_token.type == IDENT){
HashNode
* ptr;
ptr
= lookup(next_token.u.name);
lex();
if (next_token.type == OPERATOR && next_token.u.op == ' = ' ){
//
lex();
val
= expr();
ptr
-> value = val;
}
else {
val
= ptr -> value;
}
}
else { // '(',
fprintf(stderr, " unkown charactor: %c
" , next_token.u.op);
exit(
1 );
}
return val;
}

3. 문법 분석과 동시에 값을 구한다
역귀하강법의 장점 중 하나는 의미 가공에 있어 이런 방법은 매우 유연하여 하위 프로그램의 어느 곳에서든 의미 처리 프로그램을 삽입할 수 있다.
4. 오류 처리
괄호가 0을 제외하고 일치하는지 여부입니다.
카탈로그 트리
./
|-- hash.h
|-- hash.c
|-- main.c
|-- makefile
|-- front.h
어법 분석 프로그램과 문법 분석 프로그램의 헤더 파일
|-- scanner.c
어법 분석
|-- parser.c
문법 분석
|-- specification.txt
설명
`-- test.in
테스트 데이터
마지막으로 전체 패키지와 실행 프레젠테이션을 제공합니다.
http://yongmou.googlecode.com/files/calculator.zip
[lym@localhost calculator]$ make

gcc -g -Wall -c hash.c

gcc -g -Wall -c parser.c

gcc -g -Wall -c scanner.c

gcc -g -Wall -c main.c

gcc -g -Wall hash.o parser.o scanner.o main.o -o cal -lm

[lym@localhost calculator]$ ./cal

a = 10;

10.000000

b = 20;

20.000000

a + b * 5;

110.000000

a = 20;

20.000000

(a+b)*5;

200.000000

(a+b)/5;

8.000000

a = 3.14;

3.140000

a * 2 * 2;

12.560000

좋은 웹페이지 즐겨찾기