c - 如何基于 C 代码创建转换图

Question

我必须为标识符和数字的词法分析器创建转换图。

代码如下:

/* recursive factorial function */
int fact (int x )
{ 
   if (x>1)
      return x * fact (x-1); 
   else 
      return 1; 
} 

void main (void)
{
    int x;    
    x = read(); 
    if (x > 0) write (fact (x)); 
} 

我对如何创建这个图表感到有点迷失。任何人都可以为我指出正确的方向或提供可以帮助我完成这项任务的资源吗？

Answer 1

Malcolm McLean 告诉您如何在实际代码中做到这一点，但我认为您需要使用有限状态机的更具理论性的方法。

首先进行库存检查:需要什么，我们有什么符号等。示例代码中的 EBNF:

space = ? US-ASCII character 32 ?;
zero = '0';
digit = '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9';
character = 'a' | 'A' | 'b' | 'B' ... 'z' | 'Z';

(* a single digit might be zero but a number must not start with a zero (no octals) *)
integer = (digit|zero) | ( digit,{(digit|zero)});
(* identifier must start with a character *)
identifier = character,{ (digit | character) };
(* the keywords from the example, feel free to add more *)
keywords = "if" | "else" | "return" | "int" | "void";

(* TODO: line-end, tabs, etc. *)
delimiter = space, {space};

braceleft = '{';
braceright = '}';
parenleft = '(';
parenright = ')';

equal = '=';
greater = '>';
smaller = '<';

minus = '-';
product = '*';

semicolon = ';'

end = ? byte denoting EOF (end of file) ?;

现在制作一个转换表。从状态 START 开始。 START 只是开始状态，没什么特别的，没什么可做的，但我们需要从某个地方开始。所以从那里我们可以获得上述任何字符。实际上，在每个状态之后总是如此，所以我们可以进行 C&P；

START
      zero        ->  ZERO
      digit       ->  INTEGER
      character   ->  IDENTIFIER
      space       ->  START
      braceleft   ->  BRACES
      braceright  ->  BRACES
      parenleft   ->  PARENTHESES
      parenright  ->  PARENTHESES
      equal       ->  COMPARING
      greater     ->  COMPARING
      smaller     ->  COMPARING
      minus       ->  ARITHMETIC
      product     ->  ARITHMETIC
      semicolon   ->  START
      end         ->  END

ZERO
      zero        ->  ERROR (well...)
      digit       ->  ERROR
      character   ->  ERROR
      space       ->  START
      braceleft   ->  BRACES
      braceright  ->  BRACES
      parenleft   ->  PARENTHESES
      parenright  ->  PARENTHESES
      equal       ->  COMPARING
      greater     ->  COMPARING
      smaller     ->  COMPARING
      minus       ->  ARITHMETIC
      product     ->  ARITHMETIC
      semicolon   ->  START
      end         ->  END

INTEGER
      zero        ->  INTEGER
      digit       ->  INTEGER
      character   ->  ERROR
      space       ->  START
      braceleft   ->  BRACES
      braceright  ->  BRACES
      parenleft   ->  PARENTHESES
      parenright  ->  PARENTHESES
      equal       ->  COMPARING
      greater     ->  COMPARING
      smaller     ->  COMPARING
      minus       ->  ARITHMETIC
      product     ->  ARITHMETIC
      semicolon   ->  START
      end         ->  END

状态IDENTIFIER意味着我们已经有了一个字符，所以

IDENTIFIER
      zero        ->  IDENTIFIER
      digit       ->  IDENTIFIER
      character   ->  IDENTIFIER
      space       ->  START
      braceleft   ->  BRACES
      braceright  ->  BRACES
      parenleft   ->  PARENTHESES
      parenright  ->  PARENTHESES
      equal       ->  COMPARING
      greater     ->  COMPARING
      smaller     ->  COMPARING
      minus       ->  ARITHMETIC
      product     ->  ARITHMETIC
      semicolon   ->  START
      end         ->  END

除了状态ERROR之外，状态ERROR之后没有任何内容

ERROR -> ERROR

除了状态ERROR之外，状态END之后没有任何内容

END -> ERROR



ARITHMETIC
      zero        ->  ZERO
      digit       ->  INTEGER
      character   ->  IDENTIFIER
      space       ->  START
      braceleft   ->  BRACES
      braceright  ->  BRACES
      parenleft   ->  PARENTHESES
      parenright  ->  PARENTHESES
      equal       ->  COMPARING
      greater     ->  COMPARING
      smaller     ->  COMPARING
      minus       ->  ARITHMETIC
      product     ->  ARITHMETIC
      semicolon   ->  START
      end         ->  END

将计数和余额检查留给解析器

BRACES -> START
PARENTHESES -> START

COMPARING
      zero        ->  ZERO
      digit       ->  INTEGER
      character   ->  IDENTIFIER
      space       ->  START
      braceleft   ->  BRACES
      braceright  ->  BRACES
      parenleft   ->  PARENTHESES
      parenright  ->  PARENTHESES
      equal       ->  ERROR (only check for single characters here, no ">=" or similar)
      greater     ->  ERROR
      smaller     ->  ERROR
      minus       ->  ERROR
      product     ->  ERROR
      semicolon   ->  ERROR
      end         ->  ERROR

希望我没有犯任何严重错误，剩下的唯一问题是空格和关键字。以“if”为例:

字符第一次出现时

      character   ->  KEYWORDS

KEYWORDS
      'i' -> IF
      'r' -> RETURN
      ...
      any other character (exc. parens etc.) -> IDENTIFIER

IF
      'f' -> IT_IS_IF
      ...
      any other character (exc. parens etc.) -> IDENTIFIER

IT_IS_IF
      '(' -> START
      ')' -> ERROR
      '=' -> ERROR
      ...
      digit or character -> IDENTIFIER 

当然，你可以使用快捷方式来做到这一点，并将每个关键字都设置为单个符号，否则会非常乏味。我想，一点点作弊是允许的？

再次在字符第一次出现时

      character   ->  KEYWORDS

KEYWORDS
      if_symbol -> IF
      else_symbol -> ELSE
      return_symbol -> RETURN
      ...
      digit or character -> IDENTIFIER 

IF
      '(' -> PARENTHESES
      ')' -> ERROR
      '=' -> ERROR
      ...

那么，可以跳过所有空白吗？像这样的构造

return x;

是合法的

returnx;

因此，一旦您拥有完整的关键字，它要么后跟一个空格(或分号或大括号或允许在某个保留单词后的任何符号)，要么后跟一个字符/数字，使其成为标识符，或者其次是不允许的事情。其余的可以而且应该留给解析器。

或者您采用首次点击方法:一旦您有了关键字，您就返回开始，因此 returnx; 将被视为 RETURN IDENTIFIER SEMICOLON。但这会减少可能的标识符的数量，例如:ifitsone将是IF ERROR，这很可能会导致您的错误列表中出现大量愤怒的条目。

利用上面的所有信息，您可以构建表格。如果我们将行设置为州，将列设置为符号

             zero        digit     character  space  braceleft  braceright  parenleft    ...
START        ZERO       INTEGER   IDENTIFIER  START    BRACES     BRACES   PARENTHESES   ...
ZERO         ERROR       ERROR     ERROR      START    BRACES     BRACES   PARENTHESES   ...
INTEGER      INTEGER    INTEGER    ERROR      START    BRACES     BRACES   PARENTHESES   ...
IDENTIFIER  IDENTIFIER IDENTIFIER IDENTIFIER  START    BRACES     BRACES   PARENTHESES   ...
  ... 

注意:以上所有内容都非常简化，并且可能包含错误!但这基本上就是它的工作原理，并没有那么复杂，它只是有一些你必须学习的奇特名称。

刚刚看到马尔科姆·麦克莱恩的回答被认为是可以接受的，所以......