search

wandersonwhcr / romans

A Simple PHP Roman Numerals Library
MIT License
44 stars 3 forks source link

Problem with Two Tokens and Lookahead #31

Closed wandersonwhcr closed 7 years ago

wandersonwhcr commented 7 years ago

If we have two tokens with lookahead, Parser doesn't recognize as a problem, because first value is equal to current value. Example:

use Romans\Grammar\Grammar;
use Romans\Parser\Parser;

(new Parser())->parse([Grammar::T_IX, Grammar::T_IX]); // INVALID
wandersonwhcr commented 7 years ago

Added more tests to check errors.

wandersonwhcr commented 7 years ago

Thinking about the problem, I just realize that we must create a deterministic finite automaton to validate (and parse) an array of tokens.

Definition:

M  = (Q, Σ, δ, q0, F)
Q  = { z, a, b, c, d, e, f, g }
Σ  = { I, V, X, L, C, D, M }
q0 = g
F  = { z }

Transition functions:

z -> $
a -> z | Iz  | IIz | IIIz
b -> a | IVz | Va  | IXz
c -> b | Xb  | XXb | XXXb
d -> c | XLb | Lc  | XCb
e -> d | Cd  | CCd | CCCd
f -> e | CDd | De  | CMd
g -> f | Nz  | Mg