2

练习内容为“编写一个程序来检查 C 程序中的基本语法错误，例如不平衡的括号、方括号和大括号。不要忘记单引号和双引号、转义序列和注释。”

我选择通过将括号、方括号和大括号放在堆栈上来解决问题，并确保所有内容都是 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];
  }
}
4

2 回答 2

3

你的解决方案还不错。这是非常直接的，这是一件好事。为了从这个练习中学到更多，我可能会用状态机来实现它。例如，您有一些状态，例如：，code等。然后您定义它们之间的转换。它变得容易多了，因为你最终得到了取决于状态的逻辑（所以你没有代码，就像在你的 main 函数中一样）。之后，您可以根据状态解析代码。例如，这意味着：如果您处于评论状态，您会忽略所有内容，直到遇到结束评论字符。然后将状态更改为例如，依此类推。commentstringcode

在伪代码中，它可能如下所示：

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 来完成。但正如我在评论中所说，我不建议你使用它。如果您有足够的时间并想尽可能多地学习，也许您可​​以这样做，但首先我会以“艰难的方式”实施它。

于 2011-08-11T07:33:13.537 回答
2

通过使用解析器生成器（如yacc）和词法分析器生成器（如lex），我可能会以完全不同的方式处理此问题。

您可以将自己基于这些工具的现有输入文件，用于 ANSI C。此lex 规范和yacc 语法，例如。可以作为一个起点。或者，K&R 在附录 A 中也包含与 yacc 兼容的 C 语法，或者您当然可以直接使用 C 标准中的语法。

对于本练习，您将只使用您感兴趣的语法部分，而忽略其余部分。语法将确保语法正确（所有大括号都匹配等），而 lex/yacc 将负责所有代码生成。这使您只需要指定一些粘合代码，在这种情况下主要是错误消息。

它将完全重写您的代码，但可能会让您更好地理解 C 语法，并且至少，您将学会使用伟大的工具 lex/yacc，这永远不会受到伤害。

于 2011-08-11T06:17:12.393 回答