Parsing Arithmetic Expressions with Prolog Definite Clause Grammars

The Problem: Handling Structured Text Input

Parsing structured text—such as mathematical expressions or configuration files—using standard Prolog predicates often results in verbose, hard-to-maintain code involving complex list manipulation. The primary challenge is managing the 'remaining' part of the input string as it is consumed by different rules.

The solution is Definite Clause Grammars (DCGs). DCGs are a syntactic sugar in Prolog that allow you to define a grammar directly. The Prolog compiler translates these into standard predicates that use difference lists (a technique where a list is represented by two pointers: the start and the end), automatically handling the bookkeeping of which characters have been processed and which remain.

Implementing an Arithmetic Parser

To parse arithmetic expressions, you must define rules that respect the order of operations (precedence). In a DCG, this is achieved by nesting rules: expressions contain terms, and terms contain factors.

The following example demonstrates a DCG that parses basic addition and multiplication. It uses semantic actions—code wrapped in curly braces {...}—to calculate the result or build a parse tree during the parsing process.

% Define the grammar rules
% expr parses addition
expr(N) --> term(T1), [+], expr(T2), { N is T1 + T2 }.
expr(N) --> term(N).

% term parses multiplication
term(N) --> factor(F1), [*], term(F2), { N is F1 * F2 }.
term(N) --> factor(N).

% factor parses a single digit
factor(N) --> [Char], { char_code(Char, Code), Code >= 48, Code =< 57, N is Code - 48 }.

Running the Parser

To execute this grammar, use the built-in phrase/3 predicate. This predicate takes the starting rule, the input list (usually a string or list of characters), and an empty list to signify the end of the input.

Execution Steps:
1. Load the code into a Prolog interpreter (e.g., SWI-Prolog 8.x).
2. Run the following query in the console:

?- phrase(expr(Result), [0'3,0'+,0'4,0'*0'5], []).
% Expected Result: Result = 23.

Permissions and Risks: This code runs in the standard user space of any Prolog environment. The primary risk is non-termination; if the grammar is defined incorrectly, the interpreter may enter an infinite loop and exhaust the stack.

Critical Constraints and Common Failures

The Left-Recursion Trap

Prolog uses a top-down, depth-first search strategy. If you define a rule that calls itself as the first action, you create left recursion, leading to an infinite loop.

Incorrect (Infinite Loop):
expr --> expr, [+], term.

Correct (Right-Recursive):
expr --> term, [+], expr.

While right-recursion solves the loop, it changes the associativity of the operation (making it right-associative). For operations like subtraction or division where order matters, you must either use a right-recursive grammar and then reverse the resulting tree or use a specialized parser like a Tabling engine if your Prolog implementation supports it.

Mixing DCG and Standard Predicates

A common mistake is attempting to call a DCG rule as a standard predicate without accounting for the hidden arguments. A rule defined as expr --> term is actually compiled into expr(ListIn, ListOut).

If you try to call expr(Result) inside a standard Prolog predicate without using phrase/3 or providing the two list arguments, the query will fail or throw a type error.

Verification and Limitations

How to Verify Results

To ensure your parser is working correctly, test it against three scenarios:

• Positive Match: Use a valid string (e.g., [0'1,0'+,0'2]) and verify the result is mathematically correct.
• Negative Match: Use an invalid string (e.g., [0'1,0'+,0'+,0'2]). The phrase/3 predicate should return false rather than crashing.
• Partial Match: Provide a string with trailing characters (e.g., [0'1,0'+,0'2,0'a,0'b,0'c]). If the third argument of phrase/3 is [], it should fail because the entire string was not consumed.

Limitations

DCGs are primarily designed for Context-Free Grammars (CFGs). If your language requires context-sensitive checks (e.g., ensuring a variable is declared before it is used), you must pass additional state arguments through the rules manually. This increases complexity and reduces the readability that DCGs provide.