编译器构建中自动机的作用是进行词法分析和语法分析,以识别和解析源代码中的语法结构。
下面是一个简单的代码示例,展示了如何使用自动机进行词法分析和语法分析。
import re
# 定义词法规则
token_specs = [
('NUMBER', r'\d+'),
('PLUS', r'\+'),
('MINUS', r'\-'),
('TIMES', r'\*'),
('DIVIDE', r'\/'),
('LPAREN', r'\('),
('RPAREN', r'\)'),
('WS', r'\s+'),
]
# 定义Token类
class Token:
def __init__(self, type, value):
self.type = type
self.value = value
def __str__(self):
return f'Token({self.type}, {self.value})'
# 定义词法分析器
class Lexer:
def __init__(self, text):
self.text = text
self.pos = 0
def tokenize(self):
tokens = []
while self.pos < len(self.text):
match = None
for token_type, pattern in token_specs:
regex = re.compile(pattern)
match = regex.match(self.text, self.pos)
if match:
value = match.group(0)
if token_type != 'WS':
token = Token(token_type, value)
tokens.append(token)
break
if not match:
raise Exception('Invalid input')
else:
self.pos = match.end(0)
return tokens
# 定义语法分析器
class Parser:
def __init__(self, tokens):
self.tokens = tokens
self.pos = 0
def parse(self):
return self.expr()
def expr(self):
return self.term() + self.expr_tail()
def term(self):
return self.factor() * self.term_tail()
def factor(self):
token = self.tokens[self.pos]
if token.type == 'NUMBER':
self.pos += 1
return int(token.value)
elif token.type == 'LPAREN':
self.pos += 1
result = self.expr()
if self.tokens[self.pos].type == 'RPAREN':
self.pos += 1
return result
else:
raise Exception('Invalid syntax')
else:
raise Exception('Invalid syntax')
def expr_tail(self):
if self.pos < len(self.tokens) and self.tokens[self.pos].type in ('PLUS', 'MINUS'):
op = self.tokens[self.pos].type
self.pos += 1
return op + self.term() + self.expr_tail()
else:
return ''
def term_tail(self):
if self.pos < len(self.tokens) and self.tokens[self.pos].type in ('TIMES', 'DIVIDE'):
op = self.tokens[self.pos].type
self.pos += 1
return op + self.factor() + self.term_tail()
else:
return ''
# 测试代码
text = '3 + 4 * (2 - 1)'
lexer = Lexer(text)
tokens = lexer.tokenize()
print(tokens)
parser = Parser(tokens)
result = parser.parse()
print(result)
这个代码示例实现了一个简单的四则运算表达式解析器。首先,使用词法分析器(Lexer)将输入的文本解析成一系列词法单元(Token)。然后,使用语法分析器(Parser)根据词法单元构建语法树,并计算表达式的结果。在语法分析器中,使用自动机进行递归下降的语法分析。