Ниже — компактные реализации парсера арифметических выражений (целые числа, операции $+$, $-$, $\ast$, $/$, скобки) в четырёх стилях: процедурном, ООП, функциональном и логическом. Для каждого — краткое объяснение, преимущества/недостатки в поддержке расширений и отладке. Примеры: выражение $1+2\ast 3$ даёт результат $7$.
1) Процедурный (Python, рекурсивный спуск)
Код:
```python
def parse_eval(s):
s = s.replace(' ', '')
i = 0
def peek():
return s[i] if i < len(s) else ''
def consume():
nonlocal i
ch = s[i] if i < len(s) else ''
i += 1
return ch
def number():
nonlocal i
start = i
while i < len(s) and s[i].isdigit():
i += 1
return int(s[start:i])
def factor():
if peek() == '(':
consume()
v = expr()
consume() # ')'
return v
if peek() == '-':
consume()
return -factor()
return number()
def term():
v = factor()
while peek() in '*/':
op = consume()
if op == '*': v *= factor()
else: v //= factor()
return v
def expr():
v = term()
while peek() in '+-':
op = consume()
if op == '+': v += term()
else: v -= term()
return v
return expr()
# Пример:
# parse_eval("1+2*3") -> 7
```
Плюсы: простой, быстро писать и понимать; отладка шагов парсинга очевидна (поставить точки останова в функциях). Минусы: расширения (новые операторы, ассоциативности, прямиая генерация AST) требуют изменения многих функций; масштабируемость ниже.
2) ООП (Python, AST-классы)
Код:
```python
class Tokenizer:
def __init__(self, s): self.s = s.replace(' ',''); self.i=0
def peek(self): return self.s[self.i] if self.i<len(self.s) else ''
def next(self): ch=self.peek(); self.i+=1; return ch
def number(self):
start=self.i
while self.peek().isdigit(): self.i+=1
return int(self.s[start:self.i])
class Node: pass
class Num(Node):
def __init__(self,v): self.v=v
def eval(self): return self.v
class Bin(Node):
def __init__(self,op,l,r): self.op=op; self.l=l; self.r=r
def eval(self):
a=self.l.eval(); b=self.r.eval()
return {'+':a+b,'-':a-b,'*':a*b,'/':a//b}[self.op]
class Parser:
def __init__(self,s): self.t=Tokenizer(s)
def factor(self):
if self.t.peek()=='(': self.t.next(); n=self.expr(); self.t.next(); return n
if self.t.peek()=='-': self.t.next(); return Bin('*', Num(-1), self.factor())
return Num(self.t.number())
def term(self):
n=self.factor()
while self.t.peek() in '*/':
op=self.t.next(); n=Bin(op,n,self.factor())
return n
def expr(self):
n=self.term()
while self.t.peek() in '+-':
op=self.t.next(); n=Bin(op,n,self.term())
return n
# Пример:
# ast = Parser("1+2*3").expr(); ast.eval() -> 7
```
Плюсы: явный AST упрощает расширения (новые ноды, оптимизации, трансформации), легче добавлять методы (печатать, оптимизировать, генерировать код); отладка на уровне объектов. Минусы: немного больше шаблонного кода; при больших изменениях нужно расширять иерархию классов.
3) Функциональный (Haskell, парсер-комбинаторы Parsec) — компактно и декларативно
Код (Haskell):
```haskell
import Text.Parsec
import Text.Parsec.String (Parser)
import Control.Applicative (())
num :: Parser Int
num = read many1 digit
expr :: Parser Int
expr = chainl1 term ((+) <$ char '+' (-) <$ char '-')
term :: Parser Int
term = chainl1 factor ((*) <$ char '*' div <$ char '/')
factor :: Parser Int
factor = (negate <$ char '-' factor) (char '(' *> expr <* char ')') num
-- Пример:
-- parseTest expr "1+2*3" => 7
```
Плюсы: очень выразительно описывается грамматика, легко менять приоритеты и добавлять правила; парсер-комбинаторы хорошо комбинируются и тестируются; код короткий. Минусы: для тех, кто не знаком с функциональным стилем — порог вхождения; сложные состояния/побочные эффекты требуют дополнительных абстракций.
4) Логический (Prolog, DCG) — грамматика ближе к спецификации
Код (Prolog):
```prolog
% DCG: expr(Value) parses list of char codes
:- use_module(library(dcg/basics)).
expr(V) --> term(T), expr_rest(T, V).
expr_rest(Acc, V) --> "+", term(T), {Acc1 is Acc + T}, expr_rest(Acc1, V).
expr_rest(Acc, Acc) --> [] ; ("-", term(T), {Acc1 is Acc - T}, expr_rest(Acc1, Acc)).
term(V) --> factor(F), term_rest(F, V).
term_rest(Acc, V) --> "*", factor(F), {Acc1 is Acc * F}, term_rest(Acc1, V).
term_rest(Acc, Acc) --> [] ; ("/", factor(F), {Acc1 is Acc // F}, term_rest(Acc1, Acc)).
factor(V) --> "-", factor(F), {V is -F}.
factor(V) --> "(", expr(V), ")".
factor(V) --> integer(V).
% Пример запроса:
% ?- string_codes("1+2*3", Codes), phrase(expr(V), Codes).
% V = 7.
```
Плюсы: грамматика и оценка записываются декларативно; легко экспериментировать с синтаксическими правилами; удобно для прототипирования парсеров и задач анализа. Минусы: отладка DCG-приложений и управление побочными эффектами/поведением в больших системах может быть сложнее; производительность иногда хуже и специфична для Prolog.
Сравнение по поддержке расширений и отладке (кратко)
- Процедурный: прост в реализации; расширения требуют правок в структуре функций — средняя гибкость; отладка линейна и понятна.
- ООП: хорош для больших систем — легко расширять AST; отладка на уровне объектов эффективна; код более формален и масштабируем.
- Функциональный: очень гибок для грамматик и комбинирования правил; чистота функций облегчает тестирование; но требует функционального мышления.
- Логический: декларативное описание грамматики — быстро вносить синтаксические изменения; отладка логических ошибок и управление состоянием требует навыка.
Вывод: для быстрого простого парсера — процедурный стиль; для промышленного решения с трансформациями/генерацией кода — ООП; для чистых грамматик и быстрых экспериментов с приоритетами — функциональные парсер-комбинаторы; для декларативных спецификаций и прототипирования — логический (DCG).