如何基于 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

词法分析器以空或初始状态开始。它命中 "i"。所以它知道它必须有一个关键字或一个标识符。它命中 'n' 和 't' 并将它们添加到令牌中。它命中 space。所以它知道这是令牌的结尾，也就是 "int"，一个关键字。现在它达到了 'f'。同样的故事，但令牌是 "fact"，这不是关键字，所以它是一个标识符。现在 '(' - 这是一个左括号标记。所以它继续。

当它命中可能是除法标记或评论开头的“/”时，实际上它是评论的开头。所以它现在进入注释状态，直到它碰到 */。

除了其中有一些整数文字标记外，没有其他明显不同。为了方便您，没有任何条件。 main 有点特例，看词法分析器的写法，可以看做是关键字，也可以看成是普通标识符。

Answer 2

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) ?;

现在进行转换table。从状态 START 开始。 START 只是开始状态，没什么特别的，没什么可做的，但我们需要从某个地方开始。所以从那里我们可以获得上述任何字符。其实总是这样，在每个state之后，所以我们可以做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

希望我没有实施任何严重错误，剩下的唯一问题是 spaces 和关键字。例如 "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
      ...

所以，可以你直接跳过所有白色-space吗？像

这样的结构

return x;

和现在一样合法

returnx;

所以，一旦你有了一个完整的关键字，它要么后跟一个 space（或分号或大括号或任何允许在某个保留词之后的符号），要么后跟一个 character/digit 使其成为标识符，或后跟不允许的内容。剩下的可以，也应该留给解析器。

或者你采用先命中的方法：一旦你有了关键字，你就返回开始，所以 returnx; 将被视为 RETURN IDENTIFIER SEMICOLON。但这会减少可能的标识符的数量，例如：ifitsone 将是 IF ERROR，这很可能会导致您的错误列表中出现很多令人愤怒的条目。

利用以上所有信息，您可以构建 table。如果我们将行设置为状态，将列设置为符号

             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   ...
  ...

注意：以上所有内容都非常简单，可能包含错误！但这基本上就是它的工作原理，没有那么复杂，它只是有一些你必须学习的花哨的名字。

刚刚看到 Malcolm McLean 的回答被视为接受table，所以...

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

How Do You Create A Transition Diagram Based on C Code

c

compiler-construction

transition

diagram

lexical