K＆Rからの演習1-24 - 初歩的な構文チェック

Question

練習問題は、「プログラムを作成して、不均等なかっこ、かっこ、中括弧などの基本構文エラーをチェックするプログラムを作成します。エスケープシーケンス、およびコメント。

私は

など、引用、スタック上に丸括弧、角括弧、中括弧を入れて確認してくださいすべてが、我々はコメントにしているかどうかをマーキングするために各種カウンタとともにLIFOしたことによって、問題を解決するに取り掛かることにしました

問題は、私のコードがうまく機能しているにもかかわらず、構造が不十分であり、特に慣用的ではないと感じていることです。私は、構造体内で状態変数（スタック、escaped、inStringなど）を実装し、テストをサブルーチンに分解しようとしました。それはあまり役に立たなかった。エスケープされた文字などを正しく処理しながら、この問題をよりクリーンな方法で解決する方法はありますか？

#include <stdio.h> 
#include <stdlib.h> 
#define INITIALSTACK 8 
#define FALSE 0 
#define TRUE 1 

typedef struct { 
    int position; 
    int maxLength; 
    char* array; 
} stack; 

int match(char, char); 

stack create(); 
void delete(stack*); 
void push(stack*, char); 
char pop(stack*); 

int main() { 
    char c, out; 
    stack elemStack = create(); 

    int escaped, inString, inChar, inComment, startComment, i, lineNum; 
    int returnValue; 

    escaped = inString = inChar = inComment = startComment = 0; 
    lineNum = 1; 

    while ((c = getchar()) != EOF) { 
    if (c == '\n') 
     lineNum++; 

    /* Test if in escaped state or for escape character */ 
    if (escaped) { 
     escaped = FALSE; 
    } 
    else if (c == '\\') { 
     escaped = TRUE; 
    } 

    /* Test if currently in double/single quote or a comment */ 
    else if (inString) { 
     if (c == '"' && !escaped) { 
     inString = FALSE; 
     } 
    } 
    else if (inChar) { 
     if (escaped) 
     escaped = FALSE; 
     else if (c == '\'' && !escaped) { 
     inChar = FALSE; 
     } 
    } 
    else if (inComment) { 
     if (c == '*') 
     startComment = TRUE; 
     else if (c == '/' && startComment) 
     inComment = FALSE; 
     else 
     startComment = FALSE; 
    } 

    /* Test if we should be starting a comment, quote, or escaped character */ 
    else if (c == '*' && startComment) 
     inComment = TRUE; 
    else if (c == '/') 
     startComment = TRUE; 
    else if (c == '"') { 
     inString = TRUE; 
    } 
    else if (c == '\'') { 
     inChar = TRUE; 
    } 

    /* Accept the character and check braces on the stack */ 
    else { 
     startComment = FALSE; 

     if (c == '(' || c == '[' || c == '{') 
     push(&elemStack, c); 
     else if (c == ')' || c == ']' || c == '}') { 
     out = pop(&elemStack); 
     if (out == -1 || !match(out, c)) { 
      printf("Syntax error on line %d: %c matched with %c\n.", lineNum, out, c); 
      return -1; 
     } 
     } 
    } 
    } 

    if (inString || inChar) { 
    printf("Syntax error: Quote not terminated by end of file.\n"); 
    returnValue = -1; 
    } 
    else if (!elemStack.position) { 
    printf("Syntax check passed on %d line(s).\n", lineNum); 
    returnValue = 0; 
    } 
    else { 
    printf("Syntax error: Reached end of file with %d unmatched elements.\n ", 
      elemStack.position); 
    for(i = 0; i < elemStack.position; ++i) 
     printf(" %c", elemStack.array[i]); 
    printf("\n"); 
    returnValue = -1; 
    } 

    delete(&elemStack); 
    return returnValue; 
} 

int match(char left, char right) { 
    return ((left == '{' && right == '}') || 
      (left == '(' && right == ')') || 
      (left == '[' && right == ']')); 
} 

stack create() { 
    stack newStack; 
    newStack.array = malloc(INITIALSTACK * sizeof(char)); 
    newStack.maxLength = INITIALSTACK; 
    newStack.position = 0; 
    return newStack; 
} 

void delete(stack* stack) { 
    free(stack -> array); 
    stack -> array = NULL; 
} 

void push(stack* stack, char elem) { 
    if (stack -> position >= stack -> maxLength) { 
    char* newArray = malloc(2 * (stack -> maxLength) * sizeof(char)); 
    int i; 

    for (i = 0; i < stack -> maxLength; ++i) 
     newArray[i] = stack -> array[i]; 

    free(stack -> array); 
    stack -> array = newArray; 
    } 

    stack -> array[stack -> position] = elem; 
    (stack -> position)++; 
} 

char pop(stack* stack) { 
    if (!(stack -> position)) { 
    printf("Pop attempted on empty stack.\n"); 
    return -1; 
    } 
    else { 
    (stack -> position)--; 
    return stack -> array[stack -> position]; 
    } 
} 

Answer 1

解決策はそれほど悪くありません。それは非常にまっすぐで、良いことです。このエクササイズからもう少し詳しく学ぶために、私はおそらくこれをステートマシンで実装します。例えば。次のようないくつかの州があります：code、comment、stringなど。それらの間にトランジションを定義します。状態に応じてロジックが完成するので、はるかに簡単になります（メイン関数のように、コードが不揃いです）。その後、状態に応じてコードを解析できます。これは、例えば次のことを意味します。コメント状態にある場合、終了コメント文字が出現するまですべてを無視します。次に、たとえば状態をcodeに変更します。

擬似コードでは、次のようになります。これは、例えばで行うことができますもちろん

current_state = CODE 

while(...) { 

    switch(current_state) { 
     case CODE: 
     if(input == COMMENT_START) { 
      current_state = COMMENT 
      break 
     } 

     if(input == STRING_START) { 
      current_state = STRING 
      break 
     } 

     // handle your {, [, (stuff... 

     break 

     case COMMENT: 
     if(input == COMMENT_END) { 
      current_state = CODE 
      break 
     } 

     // handle comment.. i.e. ignore everything 

     break 
     case STRING: 
     // ... string stuff like above with state transitions.. 
     break 
    } 

} 

yacc。しかし、私がコメントで述べたように、私はそれを使用することを勧めません。あなたは十分な時間があり、できるだけ多くのことを学びたいと思うかもしれませんが、まずは "難しい方法"を実装します。

Answer 2

私はおそらくlexのように、レクサー・ジェネレータと組み合わせて、yaccのように、パーサジェネレータを使用することによって、まったく異なるこの近づくだろう。

これらのツールの既存の入力ファイル（ANSI Cの場合）に基づくことができます。lex specificationとyacc grammarなどがあります。出発点にすることができます。代わりに、K & Rには、付録Aのyacc互換C文法も含まれています。もちろん、C標準の文法で直接操作することもできます。

この練習では、興味のある文法の部分だけを使用し、残りは無視します。文法は構文が正しいことを確認し（すべての中カッコが一致するなど）、lex/yaccはすべてのコード生成を処理します。そのため、いくつかのグルーコードを指定するだけで済むようになります。この場合、ほとんどの場合エラーメッセージが表示されます。

あなたのコードを完全に書き直すことはできますが、おそらくC文法の理解を深めるでしょうし、少なくとも、素晴らしいツールlex/yaccを使って作業することを学んでいます。それは決して痛くない。