PEG 解析表达式文法

核心知识点讲解

PEG 的基本概念

解析表达式文法（Parsing Expression Grammar，简称PEG）是由 Bryan Ford于2004年提出的一种用于描述形式语言的文法形式。PEG的主要特点是：

  1. 无歧义：PEG是一种无歧义的文法形式，每个输入字符串最多只有一种解析方式
  2. 自顶向下：采用自顶向下的分析策略
  3. 结合了词法和语法分析：PEG可以同时处理词法和语法分析
  4. 支持递归：自然支持递归结构
  5. 表达能力强：比上下文无关文法更具表达能力
  6. 易于实现：可以通过递归下降法直接实现

PEG 与传统文法的区别

特性 PEG 上下文无关文法 (CFG)
歧义性 无歧义 可能有歧义
选择操作 有序选择（第一个匹配优先） 无序选择
循环 显式支持（*、+操作符） 通过递归实现
谓词 支持前瞻和后顾谓词 不支持
解析方向 自顶向下 可以自顶向下或自底向上
表达能力 强于CFG 标准CFG
实现方式 递归下降、Packrat解析 LR、LL、递归下降等

PEG 的语法

PEG的语法由以下基本元素组成：

  1. 字面量：匹配具体的字符串，如 "if"、"+" 等
  2. 非终结符：引用其他规则，如 Expression、Statement 等
  3. 选择：e1 / e2，尝试匹配e1，如果失败则匹配e2
  4. 序列：e1 e2，匹配e1后接着匹配e2
  5. 零或多次：e*，匹配e零次或多次
  6. 一次或多次：e+，匹配e一次或多次
  7. 零或一次：e?，匹配e零次或一次
  8. 前瞻肯定：&e，如果e匹配则成功，但不消耗输入
  9. 前瞻否定：!e，如果e不匹配则成功，但不消耗输入

PEG 的工作原理

PEG的工作原理基于自顶向下的递归下降分析，结合了Packrat解析技术来优化性能。基本步骤如下：

  1. 规则定义：定义一系列解析规则，每个规则对应一个非终结符
  2. 递归下降：从起始规则开始，递归地尝试匹配输入字符串
  3. 有序选择：当遇到选择操作时，按照顺序尝试每个选项，第一个成功的选项被使用
  4. 记忆化：使用Packrat解析技术，缓存已解析的结果，避免重复计算
  5. 回溯：当匹配失败时，回溯到之前的状态，尝试其他可能的匹配方式

实用案例分析

示例 1：PEG 语法定义

以下是一个简单的算术表达式PEG语法：

Expression    <- Term ("+" / "-") Term*
Term          <- Factor ("*" / "/") Factor*
Factor        <- Number / "(" Expression ")"
Number        <- [0-9]+

这个语法定义了基本的算术表达式，包括加减乘除运算和括号。

示例 2：PEG 解析器实现

我们可以使用Python实现一个简单的PEG解析器：

代码实现：PEG解析器框架

# peg_parser.py

class PEGParser:
    def __init__(self, grammar, start_rule):
        self.grammar = grammar  # 文法规则
        self.start_rule = start_rule  # 起始规则
        self.memo = {}  # 记忆化缓存
    
    def parse(self, input_string):
        """
        解析输入字符串
        """
        self.memo = {}  # 重置缓存
        result, position = self.match_rule(self.start_rule, input_string, 0)
        if result is not None and position == len(input_string):
            return result
        raise SyntaxError("Syntax error")
    
    def match_rule(self, rule_name, input_string, position):
        """
        匹配规则
        """
        # 检查缓存
        key = (rule_name, position)
        if key in self.memo:
            return self.memo[key]
        
        # 获取规则定义
        rule = self.grammar[rule_name]
        
        # 匹配规则
        result, new_position = self.match_expr(rule, input_string, position)
        
        # 缓存结果
        self.memo[key] = (result, new_position)
        return result, new_position
    
    def match_expr(self, expr, input_string, position):
        """
        匹配表达式
        """
        if isinstance(expr, str):
            # 字面量匹配
            if input_string.startswith(expr, position):
                return expr, position + len(expr)
            return None, position
        elif isinstance(expr, tuple):
            # 复合表达式
            op = expr[0]
            if op == 'seq':
                # 序列匹配
                results = []
                current_pos = position
                for sub_expr in expr[1:]:
                    result, current_pos = self.match_expr(sub_expr, input_string, current_pos)
                    if result is None:
                        return None, position
                    results.append(result)
                return results, current_pos
            elif op == 'choice':
                # 选择匹配
                for sub_expr in expr[1:]:
                    result, new_position = self.match_expr(sub_expr, input_string, position)
                    if result is not None:
                        return result, new_position
                return None, position
            elif op == 'star':
                # 零或多次匹配
                results = []
                current_pos = position
                while True:
                    result, new_position = self.match_expr(expr[1], input_string, current_pos)
                    if result is None:
                        break
                    results.append(result)
                    current_pos = new_position
                return results, current_pos
            elif op == 'plus':
                # 一次或多次匹配
                results = []
                current_pos = position
                result, new_position = self.match_expr(expr[1], input_string, current_pos)
                if result is None:
                    return None, position
                results.append(result)
                current_pos = new_position
                while True:
                    result, new_position = self.match_expr(expr[1], input_string, current_pos)
                    if result is None:
                        break
                    results.append(result)
                    current_pos = new_position
                return results, current_pos
            elif op == 'opt':
                # 零或一次匹配
                result, new_position = self.match_expr(expr[1], input_string, position)
                if result is not None:
                    return result, new_position
                return None, position
            elif op == 'and':
                # 前瞻肯定
                result, _ = self.match_expr(expr[1], input_string, position)
                if result is not None:
                    return None, position
                return None, position
            elif op == 'not':
                # 前瞻否定
                result, _ = self.match_expr(expr[1], input_string, position)
                if result is None:
                    return None, position
                return None, position
        elif isinstance(expr, list):
            # 字符类匹配
            if position < len(input_string) and input_string[position] in expr:
                return input_string[position], position + 1
            return None, position
        else:
            # 非终结符匹配
            return self.match_rule(expr, input_string, position)

示例 3：使用 PEG 解析算术表达式

代码实现：解析算术表达式

# test_peg.py
from peg_parser import PEGParser

# 定义算术表达式的PEG语法
grammar = {
    'Expression': ('choice',
        ('seq', 'Term', ('star', ('seq', ('choice', '+', '-'), 'Term')))
    ),
    'Term': ('choice',
        ('seq', 'Factor', ('star', ('seq', ('choice', '*', '/'), 'Factor')))
    ),
    'Factor': ('choice',
        'Number',
        ('seq', '(', 'Expression', ')')
    ),
    'Number': ('plus', ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'])
}

# 创建PEG解析器
parser = PEGParser(grammar, 'Expression')

# 测试有效表达式
print("Testing valid expressions:")
test_cases = [
    "1",
    "1+2",
    "1+2*3",
    "(1+2)*3",
    "1-(2+3)/4"
]

for test in test_cases:
    try:
        result = parser.parse(test)
        print(f"'{test}': {result}")
    except SyntaxError as e:
        print(f"'{test}': {e}")

# 测试无效表达式
print("\nTesting invalid expressions:")
invalid_cases = [
    "1+",
    "1+*2",
    "(1+2",
    "1+(2*3"
]

for test in invalid_cases:
    try:
        result = parser.parse(test)
        print(f"'{test}': {result}")
    except SyntaxError as e:
        print(f"'{test}': {e}")

PEG 的高级特性

1. 谓词操作

PEG支持前瞻和后顾谓词，用于更精确地控制匹配：

# 前瞻肯定：匹配后面跟着if的标识符
Identifier <- !"if" [a-zA-Z_][a-zA-Z0-9_]*

# 前瞻否定：匹配后面不跟着数字的标识符
Identifier <- [a-zA-Z_][a-zA-Z0-9_]* ![0-9]

2. 左递归处理

虽然PEG自然支持递归，但直接的左递归会导致无限递归。我们可以通过以下方式处理左递归：

# 直接左递归（会导致无限递归）
Expression <- Expression "+" Term / Term

# 改写为右递归
Expression <- Term Expression'
Expression' <- "+" Term Expression' / "-" Term Expression' / ε

3. Packrat 解析

Packrat解析是一种用于PEG的高效解析技术，通过记忆化缓存避免重复计算：

def packrat_parse(self, input_string):
    """
    使用Packrat解析技术解析输入字符串
    """
    # 初始化记忆化缓存
    self.cache = {}
    # 从起始规则开始解析
    result, position = self.parse_rule(self.start_rule, input_string, 0)
    # 检查是否完全匹配
    if result is not None and position == len(input_string):
        return result
    raise SyntaxError("Syntax error")

def parse_rule(self, rule_name, input_string, position):
    """
    解析规则，使用记忆化缓存
    """
    # 检查缓存
    key = (rule_name, position)
    if key in self.cache:
        return self.cache[key]
    
    # 解析规则
    rule = self.grammar[rule_name]
    result, new_position = self.parse_expression(rule, input_string, position)
    
    # 缓存结果
    self.cache[key] = (result, new_position)
    return result, new_position

PEG 的应用场景

1. 编程语言设计

PEG非常适合设计和实现编程语言的解析器：

  • 简洁的语法定义：PEG的语法定义非常简洁明了
  • 无歧义：避免了二义性问题
  • 强大的表达能力：可以处理复杂的语法结构
  • 易于实现：可以通过递归下降法直接实现

2. 配置文件解析

PEG可以用于解析各种配置文件格式：

  • 灵活的语法：支持灵活的配置文件语法
  • 错误处理：可以提供详细的错误信息
  • 易于扩展：可以轻松扩展语法以支持新的配置选项

3. 领域特定语言（DSL）

PEG是实现领域特定语言的理想选择：

  • 快速开发：可以快速开发DSL的解析器
  • 语法灵活性：支持灵活的DSL语法
  • 强大的表达能力：可以表达复杂的领域规则

4. 自然语言处理

虽然PEG主要用于形式语言，但也可以用于简单的自然语言处理任务：

  • 短语解析：解析特定领域的短语
  • 模板匹配：匹配特定模式的句子
  • 命令解析：解析自然语言命令

代码优化与扩展

1. 错误处理改进

添加更详细的错误处理和错误报告：

def parse_with_error(self, input_string):
    """
    解析并报告详细的错误信息
    """
    try:
        return self.parse(input_string)
    except SyntaxError:
        # 找到最接近的匹配位置
        best_position = 0
        best_rule = self.start_rule
        
        for position in range(len(input_string) + 1):
            for rule_name in self.grammar:
                try:
                    result, new_position = self.match_rule(rule_name, input_string, position)
                    if new_position > best_position:
                        best_position = new_position
                        best_rule = rule_name
                except:
                    pass
        
        # 生成错误信息
        error_pos = best_position
        expected = self.get_expected_symbols(input_string, error_pos)
        raise SyntaxError(
            f"Syntax error at position {error_pos}:\n"
            f"Input: {input_string}\n"
            f"Error: {' ' * error_pos}^\n"
            f"Expected: {expected}"
        )

def get_expected_symbols(self, input_string, position):
    """
    获取在给定位置期望的符号
    """
    expected = set()
    # 分析起始规则，找出可能的下一个符号
    # ...
    return expected

2. 解析树构建

扩展PEG解析器，构建解析树：

def build_parse_tree(self, input_string):
    """
    构建解析树
    """
    self.cache = {}
    result, position = self.parse_rule_with_tree(self.start_rule, input_string, 0)
    if result is not None and position == len(input_string):
        return result
    raise SyntaxError("Syntax error")

def parse_rule_with_tree(self, rule_name, input_string, position):
    """
    解析规则并构建解析树
    """
    key = (rule_name, position)
    if key in self.cache:
        return self.cache[key]
    
    rule = self.grammar[rule_name]
    result, new_position = self.parse_expression_with_tree(rule, input_string, position)
    
    if result is not None:
        # 构建规则节点
        node = {
            'type': 'rule',
            'name': rule_name,
            'children': result
        }
        self.cache[key] = (node, new_position)
        return node, new_position
    
    self.cache[key] = (None, position)
    return None, position

3. 性能优化

进一步优化PEG解析器的性能：

def optimized_parse(self, input_string):
    """
    优化的解析方法
    """
    # 预计算输入长度
    n = len(input_string)
    # 初始化缓存
    self.cache = {}
    # 使用更高效的缓存键
    def cache_key(rule_name, pos):
        return hash((rule_name, pos)) % 1000000  # 使用哈希值作为缓存键
    
    def parse(rule_name, pos):
        key = cache_key(rule_name, pos)
        if key in self.cache:
            return self.cache[key]
        
        rule = self.grammar[rule_name]
        result, new_pos = self.parse_expr(rule, input_string, pos)
        
        self.cache[key] = (result, new_pos)
        return result, new_pos
    
    result, position = parse(self.start_rule, 0)
    if result is not None and position == n:
        return result
    raise SyntaxError("Syntax error")

主流 PEG 解析器生成器

1. PEG.js

PEG.js是一个用JavaScript实现的PEG解析器生成器：

  • 在线编辑器：提供在线编辑器，方便测试语法
  • 生成JavaScript代码：生成高效的JavaScript解析器
  • 支持语义动作：可以在语法中嵌入JavaScript代码

2. PyParsing

PyParsing是Python的一个PEG解析库：

  • 纯Python实现：完全用Python实现
  • 易于使用：提供直观的API
  • 强大的表达能力：支持复杂的语法结构

3. ANTLR 4

ANTLR 4支持PEG-like的语法：

  • 强大的工具链：提供完整的工具链
  • 多语言支持：生成多种语言的解析器
  • 支持语义谓词：支持复杂的语义谓词

4. Parslet

Parslet是Ruby的PEG解析库：

  • 纯Ruby实现：完全用Ruby实现
  • 声明式语法：提供声明式的语法定义
  • 易于扩展：易于扩展和定制

总结

本集我们学习了PEG（解析表达式文法）的基本概念、原理和应用，包括：

  1. PEG 的基本概念：无歧义的文法形式，采用自顶向下的分析策略
  2. PEG 与传统文法的区别：无歧义、有序选择、支持谓词等
  3. PEG 的语法：字面量、非终结符、选择、序列、循环等操作符
  4. PEG 的工作原理：基于自顶向下的递归下降分析，结合Packrat解析技术
  5. PEG 的高级特性：谓词操作、左递归处理、Packrat解析
  6. PEG 的应用场景：编程语言设计、配置文件解析、领域特定语言、自然语言处理
  7. 代码优化与扩展：错误处理改进、解析树构建、性能优化
  8. 主流 PEG 解析器生成器：PEG.js、PyParsing、ANTLR 4、Parslet

PEG是一种强大的文法形式，它的无歧义性和表达能力使其成为许多解析任务的理想选择。特别是在需要处理复杂语法结构的场景下，PEG提供了一种简洁、直观的方式来定义和实现解析器。

随着PEG的不断发展和普及，它在编译器设计、领域特定语言实现、配置文件解析等领域的应用将会越来越广泛。PEG的出现为语法分析领域提供了一种新的思路，使得解析器的设计和实现变得更加简单和高效。

« 上一篇 Earley 分析法简介 下一篇 » 组合子解析
↑