Syntax checker
题目
In a certain programming language (Ada) identifiers are defined by the syntax diagram (railroad chart) opposite. Transform the syntax diagram into a system of syntax diagrams which do not contain loops; i.e. which are purely recursive. Using these modified diagrams, write a predicate identifier/1 that can check whether or not a given string is a legal identifier.
% identifier(Str) :- Str is a legal identifier
解题
确定有限状态自动机或确定有限自动机（英语：deterministic finite automaton, DFA）是很有力的语法解析工具。
确定有限状态自动机
在计算理论中，确定有限状态自动机或确定有限自动机（英语：deterministic finite automaton, DFA）是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表的字元，它都能根据事先给定的转移函式转移到下一个状态（这个状态可以是先前那个状态）。
定义
确定有限状态自动机是由
- 一个非空有限的状态集合
- 一个输入字母表（非空有限的字元集合）
- 一个转移函式（例如：）
- 一个开始状态
- 一个接受状态的集合
所组成的5-元组。因此一个DFA可以写成这样的形式： 。
工作方式（非正式的语意）
确定有限状态自动机从起始状态开始，一个字元接一个字元地读入一个字串（这里的 指示Kleene星号算子。），并根据给定的转移函式一步一步地转移至下一个状态。在读完该字串后，如果该自动机停在一个属于F的接受状态，那么它就接受该字串，反之则拒绝该字串。
工作方式（正式的语意）
对于一个确定有限状态自动机，如果，我们就说该自动机接受字串w，反之则表明该自动机拒绝字串w。
被一个确定有限自动机接受的语言（或者叫「被辨识的语言」）定义为：，也就是由所有被接受的字串组成的集合。
用DFA对标识符语法建模
- 一个非空有限的状态集合
- 一个输入字母表，其中letter是英文字母集合，digit是数字集合
- 一个转移函式
|
INITIALIZED |
LETTER |
HYPHEN |
DIGIT |
INVALID |
| letter |
LETTER |
LETTER |
LETTER |
LETTER |
INVALID |
| hyphen |
INVALID |
HYPHEN |
INVALID |
HYPHEN |
INVALID |
| digit |
INVALID |
DIGIT |
DIGIT |
DIGIT |
INVALID |
| other |
INVALID |
INVALID |
INVALID |
INVALID |
INVALID |
代码实现
INITIALIZED = 'INITIALIZED'
LETTER = 'LETTER'
HYPHEN = 'HYPHEN'
DIGIT = 'DIGIT'
INVALID = 'INVALID'
def identifier(expr):
syntaxChecker = DFA(syntaxDfaTransition, INITIALIZED,
set([LETTER, DIGIT]))
for s in expr:
syntaxChecker.input(s)
return syntaxChecker.isAcceptable()
class DFA:
def __init__(self, transition, startState, acceptStates):
self.transition = transition
self.state = startState
self.acceptStates = acceptStates
def input(self, s):
self.state = self.transition(self.state, s)
def isAcceptable(self):
return self.state in self.acceptStates
def syntaxDfaTransition(state, event):
if state == INITIALIZED and isLetter(event):
return LETTER
if state == INITIALIZED and isHyphen(event):
return INVALID
if state == INITIALIZED and isDigit(event):
return INVALID
if state == INITIALIZED and isOther(event):
return INVALID
if state == LETTER and isLetter(event):
return LETTER
if state == LETTER and isHyphen(event):
return HYPHEN
if state == LETTER and isDigit(event):
return DIGIT
if state == LETTER and isOther(event):
return INVALID
if state == HYPHEN and isLetter(event):
return LETTER
if state == HYPHEN and isHyphen(event):
return INVALID
if state == HYPHEN and isDigit(event):
return DIGIT
if state == HYPHEN and isOther(event):
return INVALID
if state == DIGIT and isLetter(event):
return LETTER
if state == DIGIT and isHyphen(event):
return HYPHEN
if state == DIGIT and isDigit(event):
return DIGIT
if state == DIGIT and isOther(event):
return INVALID
if state == INVALID and isLetter(event):
return INVALID
if state == INVALID and isHyphen(event):
return INVALID
if state == INVALID and isDigit(event):
return INVALID
if state == INVALID and isOther(event):
return INVALID
def isLetter(event):
return event.isalpha()
def isHyphen(event):
return event == '-'
def isDigit(event):
return event.isdigit()
def isOther(event):
return not (isLetter(event) or isHyphen(event) or isDigit(event))
参考