含正则重复的语法如何用LR(k)等算法解析并构建语法树？

Great question! Regular-style repetition operators like + (one or more) and * (zero or more) are ubiquitous in practical grammar definitions, but they aren't part of standard context-free grammar (CFG) notation. Let's walk through how to handle this—starting with LR(k) parsing, since that's what you're familiar with, then covering other common approaches.

Step 1: Convert Repetition Rules to Standard CFGs #

LR(k) parsers only work with context-free grammars, so the first step is to translate your repetition-based rule into equivalent CFG productions. For your example rule:

S -> ( E ';' )+

The + operator means "one or more instances of E ';'". We can rewrite this with two standard CFG rules:

S -> E ';' S'
S' -> E ';' S' | ε  // ε represents the empty string

Or a more readable alternative (which avoids the empty production if you prefer):

S -> E ';' | E ';' S

Both versions capture the "one or more" semantics: the first rule handles the mandatory first instance, and the second rule allows adding additional repetitions.

Parsing with LR(k) & Building the Syntax Tree #

Once you've converted the rule to CFG, you can proceed with standard LR(k) parsing (e.g., building an LR(1) table, performing shift-reduce actions). The key part is adjusting your syntax tree construction during reduction steps:

• When you reduce an E ';' pair (as part of building S or S'), create a child node representing that single E element (you can ignore the ; in the tree if it's just a separator, or include it if needed).
• For reductions of S' -> E ';' S', take the existing S' node and append the new E child to its list of elements.
• Finally, when reducing S -> E ';' S', combine the initial E and all elements from S' into a single S node that represents the entire repeated sequence.

For example, given the input e; e;, your syntax tree would look like:

S
├─ E (value: 'e')
└─ E (value: 'e')

(If you choose to include the ; nodes, they'd be siblings to each E.)

Using Parser Generators with Built-in Repetition Support #

Most modern parser generators (like Bison, Yacc, or ANTLR) let you use regular-style repetition operators directly in your grammar—they handle the CFG conversion automatically behind the scenes. For example, in Bison you can write:

S: (E ';')+ {
    // Action to build the syntax tree:
    // $$ = create_S_node();
    // for each matched E in the repetition:
    //   add_child($$, $E_node);
}

These tools often provide access to the list of matched subtrees from the repetition, making it easy to aggregate them into a single parent node for your syntax tree.

Alternative: Recursive Descent Parsing #

If you're writing a hand-built parser instead of using LR(k), recursive descent is a straightforward way to handle repetition. For the S rule, you'd write a function like this (pseudocode):

def parse_S():
    s_node = create_S_node()
    # Parse the mandatory first E ';'
    e_node = parse_E()
    match(';')
    add_child(s_node, e_node)
    # Parse additional E ';' pairs until none are left
    while lookahead_is('e'):  # Or whatever token starts E
        e_node = parse_E()
        match(';')
        add_child(s_node, e_node)
    return s_node

This approach is intuitive and gives you direct control over building the syntax tree as you parse each repetition.

Key Takeaways #

• For LR(k), always convert repetition operators to equivalent CFG rules first—this keeps the parser compatible with standard LR algorithms.
• Parser generators simplify this by hiding the CFG conversion, letting you use natural repetition syntax.
• Recursive descent is great for hand-written parsers, as it directly maps the repetition semantics to a loop in code.

内容的提问来源于stack exchange，提问作者Hexception