Rules

Rules In CDTk

In CDTk, grammar rules are the core of parsing logic. They define how tokens combine into higher-level structures (like expressions or statements) and ultimately form an Abstract Syntax Tree (AST). A RuleSet groups all the grammar rules for your language and is part of the pipeline after tokenization.

---

What Are Grammar Rules?

A grammar rule specifies:

1. Input Structure: Defines the sequence or pattern of tokens that the rule matches.
2. Action: Details the construction of structured objects, such as AST nodes, from the input tokens.

For example:

var rules = new RuleSet
{
    new Rule<AssignmentNode>("variable:@Identifier '=' value:@Number")
        .Returns<AssignmentNode>("variable", "value")
};

Components:

• Pattern: Describes the structure of tokens (e.g., @Identifier '=' @Number).
• Returns: Indicates the type of AST node to produce and the fields to populate.

---

Defining Rules with RuleSet

Rules are grouped into a RuleSet, and you use the new Rule<T>() API to define each rule. Here’s the basic syntax:

var rules = new RuleSet
{
    new Rule<NodeType>("Grammar Pattern")
        .Returns<NodeType>("field1", "field2")
};

• NodeType: The type of AST node to generate for this rule.
• Grammar Pattern: The formal definition of the structure using tokens and sub-rules.
• Returns: Maps tokens and rule outputs to fields of the AST node.

---

Rule Grammar

CDTk uses a declarative grammar syntax for rules. Here's what each part means:

Rule Syntax

Symbol	Description
@TokenName	Matches a token defined in the TokenSet.
RuleName	References another rule.
'='	Matches a literal string or operator.
`	`
*	Matches zero or more repetitions.
+	Matches one or more repetitions.
?	Matches zero or one occurrence.

Example Patterns

1. Basic Rule:

   new Rule<Expression>("term:Term '+' term:Term")
       .Returns<Expression>("term1", "term2")

2. Repetition:

   new Rule<Expression>("terms:Term+")
       .Returns<Expression>("terms")

3. Optional Components:

   new Rule<Statement>("expr:Expression ';'?")
       .Returns<Statement>("expr")

4. Alternation (OR):

   new Rule<Factor>("number:@Number | '(' expr:Expression ')'")
       .Returns<Factor>("value")

---

AST Node Construction

Rules can specify how the output AST is constructed by mapping fields to token values or sub-rule outputs.

Example: Mapping Fields

new Rule<AssignmentNode>("variable:@Identifier '=' value:@Number")
    .Returns<AssignmentNode>("variable", "value");

• variable: The @Identifier token is mapped to this field.
• value: The @Number token is mapped to this field.

Complex AST Structures

Rules can also construct tree-like AST structures using nested patterns:

new Rule<Expression>("left:Expression '+' right:Term")
    .Returns<Expression>("left", "right");

---

Introducing Scope-Aware Rules

Grammar rules can be made scope-aware to ensure proper context resolution when parsing. This feature is particularly useful when dealing with variable declarations, function bodies, or nested structures.

Declaring Scope Rules

var scopedRules = new RuleSet
{
    new Rule<Program>("statements:Statement+")
        .Returns<Program>("statements"),
    
    new Rule<Function>("'function' name:@Identifier args:Arguments body:Block")
        .Returns<Function>("name", "args", "body")
        .Validate((ctx, node, cancellationToken) =>
        {
            ctx.CurrentScope.Declare(node.GetString("name"));
        }),

    new Rule<Block>("'{' statements:Statement* '}'")
        .Returns<Block>("statements")
        .Validate((ctx, node, _) =>
        {
            ctx.PushScope();
            foreach (var statement in node.GetNodes("statements"))
                ctx.Eval(statement.Node, CancellationToken.None);
            ctx.PopScope();
        })
};

How It Works

• Validate Hooks: These rules inject validation logic into the parsing process, leveraging the context (e.g., ctx.PushScope() and ctx.Declare()).
• Scopes:
  • Support nested declarations within blocks.
  • Check variable usage against declared scopes.

---

Chaining and Nesting Rules

Rules can reference other rules, enabling complex, hierarchical grammar definitions.

Example: Nested Expression

new Rule<Expression>("left:Term addop:('+' | '-') right:Term")
    .Returns<Expression>("left", "addop", "right");

new Rule<Term>("left:Factor mulop:('*' | '/') right:Factor")
    .Returns<Term>("left", "mulop", "right");

new Rule<Factor>("@Number | '(' expr:Expression ')'")
    .Returns<Factor>("value");

---

Order and Priority

Rule evaluation follows the order in which rules are defined. Place more specific patterns before general ones.

Example

// Correct Order: Keyword before Identifier
new Rule<Keyword>("keyword:'if'");
new Rule<Identifier>("id:@Identifier");

---

Best Practices for Writing Rules

1. Keep it Simple: Define one pattern at a time to improve readability and maintainability.
2. Prioritize Specificity: Handle edge cases and corner patterns explicitly, especially if they overlap with generic rules.
3. Test Rules Thoroughly: Validate grammar for all supported inputs as well as edge cases.
4. Use Returns Consistently: Ensure all patterns populate AST fields correctly.
5. Incorporate Scopes for Context-Sensitive Constructs: Use Validate hooks to manage symbol declarations and usage efficiently.

---

Debugging Grammar Rules

If a rule doesn't work as expected:

• Validate the TokenSet: Ensure tokens are matched correctly in the tokenizer.
• Check Rule Order: Ensure specific rules are defined before broader patterns.
• Analyze Rule Patterns: Test each rule independently with various inputs.

Use CDTk's debugging tools to inspect the Abstract Syntax Tree (AST) and validate scope management effectively.

---

Next Steps

Now that you understand how to define and use grammar rules:

• Learn about tokenization: Tokens
• Explore AST construction: AST
• Dive into scope-aware grammar management: Scopes