Как записать синтаксический анализатор с рекурсивным спуском с нуля?
Тем не менее, было показано, что MD5 не является устойчивым к столкновениям
2 ответа
Знаете ли вы о языковых грамматиках?
Предполагая, что да, у вас есть грамматика с правилами, подобными
...
addTerm := mulTerm addOp addTerm
| mulTerm
addOp := XPlus | XMinus
mulTerm := litOrParen mulOp mulTerm
| litOrParen
...
, которые в конечном итоге превращаются в код вроде (написание кода в браузере, никогда не компилируемого )
let rec AddTerm() =
let mulTerm = MulTerm() // will parse next mul term (error if fails to parse)
match TryAddOp with // peek ahead in token stream to try parse
| None -> mulTerm // next token was not prefix for addOp rule, stop here
| Some(ao) -> // did parse an addOp
let rhsMulTerm = MulTerm()
match ao with
| XPlus -> Add(mulTerm, rhsMulTerm)
| XMinus -> Sub(mulTerm, rhsMulTerm)
and TryAddOp() =
let next = tokens.Peek()
match next with
| XPlus | XMinus ->
tokens.ConsumeNext()
Some(next)
| _ -> None
...
Надеюсь, вы поняли основную идею. Это предполагает глобальный изменяемый поток токенов, который позволяет как «заглядывать в следующий токен», так и «использовать следующий токен».
Если я помню, когда я учился в колледже, идея заключалась в том, чтобы построить деревья выражений вроде:
<program> --> <expression> <op> <expression> | <expression>
<expression> --> (<expression>) | <constant>
<op> --> * | - | + | /
<constant> --> <constant><constant> | [0-9]
, а затем, как только вы построите свое дерево полностью , вы получите что-то вроде:
exp
exp op exp
5 + and so on
затем вы запускаете законченное дерево через другую программу, которая рекурсивно спускается в дерево, вычисляя выражения, пока не получите ответ. Если ваш парсер не понимает дерево, у вас есть синтаксическая ошибка. Надеюсь, это поможет.