Ещё одно средство распознавания языков 4

[xGromMx]

А что по поводу этого? www.jetbrains.com/mps

[InWake]

Мощно! Правда JAVA

[Razaz]

То же намаялся с ANTLR. Хотел прикрутить его для парсинга фильтров в WebApi. В результате портировал кусок из ApacheDS Escimo и допилил его)
Жаль что поддержка на C# слабая, так как в целом — классная штука.

[InWake]

Примеров на c# не достать, правда их можно транслировать с JAVA примеров

[LightSUN]

Ещё можно использовать gplex / gppg. Это аналог yacc/lex но для C#. Пробовал для небольшого приложения — вполне нормально работает.

[InWake]

в документации пример 7.3 Tree-Building Calculator
калькуляторы, куда ж без них. Нужно будет посмотреть спасибо!

[LightSUN]

Вот ещё работающий пример калькулятора :).

[InWake]

что то мне не нравиться сгенерированный парсер, понятно что он авто, но вот поиск ошибок будет затруднен

states[0] = new State(new int[]{28,27,8,31,9,35,10,39,11,43,12,47,13,51,14,55,15,59,16,63,17,67,18,71,19,75,20,79,21,83,22,87,23,91,24,95,25,99,26,103,3,108,4,109,5,110,6,112,7,113,39,114,32,116,31,118},new int[]{-1,1,-3,3,-4,30,-5,107,-6,111});
    states[1] = new State(new int[]{2,2});
    states[2] = new State(-1);

и так 150 строк не перевариваемого кода. можно захлебнуться

[Mingun]

Если хочется иметь читаемый парсер, я бы порекомендовал посмотреть в сторону PEG-парсеров, для C#, например, на Pegasus.

[xGromMx]

Тогда уж лучше Nemerle rsdn.ru/article/nemerle/PegGrammar.xml он для этого предназначен

[InWake]

Левая рекурсия

PEG фактически описывает нисходящий рекурсивный парсер с откатами. Этот тип парсеров имеет одно ограничение. Без специальной доработки (негативно влияющей на производительность и сильно усложняющей парсер) парсеры этого типа не могут разбирать леворекурсивные грамматики.

Леворекурсивной грамматикой называют грамматику, которая имеет леворекурсивные правила (прямые или нет). Например, следующая грамматика имеет левую рекурсию:

X = X '+' 1 / 1

…
Научно доказано, что любое леворекурсивное правило можно переписать без левой рекурсии. Например, приведенное выше правило можно переписать так:

X = 1 ('+' 1)*

я не очень знаком с грамматиками

expr : expr ('*'|'/') expr   # MulDiv
     | expr ('+'|'-') expr   # AddSub
     | INT                  # int
     | '(' expr ')'         # parens
     ;

очевидно левая рекурсия, но как от нее избавиться?

[InWake]

что то очень не привычная грамматика (да же смешивание грамматики с парсером, хотя и более читаемая чем массивы)

@namespace MyProject
@classname ExpressionParser

additive <decimal> -memoize
    = left:additive "+" right:multiplicative { left + right }
    / left:additive "-" right:multiplicative { left - right }
    / multiplicative

multiplicative <decimal> -memoize
    = left:multiplicative "*" right:primary { left * right }
    / left:multiplicative "/" right:primary { left / right }
    / primary

primary <decimal>
    = decimal
    / "(" additive:additive ")" { additive }

decimal <decimal>
    = value:([0-9]+ ("." [0-9]+)?) { decimal.Parse(value) }

когда примерно то же самое в antlr

grammar Calculator;
 
/*
 * Parser Rules
 */
 
prog: expr+ ;
 
expr : left = expr op=('*'|'/') right = expr   # MulDiv
     | left = expr op=('+'|'-') right = expr   # AddSub
     | INT                  # int
     | '(' expr ')'         # parens
     ;
 
/*
 * Lexer Rules
 */
INT : [0-9]+;
ADD : '+';
MUL : '*';

WS
    :   (' ' | '\r' | '\n') -> channel(HIDDEN)
    ;

а если убрать весь шум (помогающий обходить дерево)

grammar Calculator;
 
prog: expr+ ;
 
expr : expr ('*'|'/') expr   # MulDiv
     | expr ('+'|'-') expr   # AddSub
     | INT                  # int
     | '(' expr ')'         # parens
     ;
 
INT : [0-9]+;

WS
    :   (' ' | '\r' | '\n') -> channel(HIDDEN)
    ;

хотя обход нужно писать отдельно (но за разделение ответственности нужно платить)