Разработка простого анализатора

Моя дневная работа включает работу по созданию компилятора, подобного Pascal. Я постоянно работаю над оптимизацией и генерированием кода.

Я также хотел бы начать учиться создавать простой парсер для одного и того же языка. Я, однако, не совсем уверен, как это сделать. Кажется, выбор Flex и Bison. Но нельзя ли писать парсер с использованием С++ или С#? Я немного жуткий с C.

YacС++ поддерживает С#, но он лицензирован. Я ищу всю помощь, которую я могу найти в этом отношении. Предложения будут высоко оценены.

9 ответов

Я считаю, что вы можете использовать ANTLR с С#. Я никогда не пробовал это сам (пока), однако есть учебник здесь, который может указывать на вас в правильном направлении.


Лично я просматриваю свой лексер и парсер (LL). Здесь очень сокращенный пример. Он находится на С++, но, надеюсь, вы сможете его адаптировать. Он использует макрос PARSE_HIGHER, чтобы упростить вставку операторов на разных уровнях приоритета без значительного изменения кода.

// routine to scan over whitespace/comments
void ScanWhite(const char* &pc){
 while(true){
 if(0);
 else if (WHITESPACE(*pc)) pc++;
 else if (pc[0]=='/' && pc[1]=='/'){
 while(*pc && *pc++ != '\n');
 }
 else break;
 }
}
// routine to lex an identifier
bool SeeId(const char* &pc, string sId){
 ScanWhite(pc);
 const char* pc0 = pc;
 if (alpha(*pc)){
 sId = "";
 while(alphanum(*pc)) sId += (*pc++);
 return true;
 }
 pc = pc0;
 return false;
}
// routine to lex a number
bool SeeNum(const char* &pc, ****** &dNum){
 ScanWhite(pc);
 const char* pc0 = pc;
 if (digit(*pc)){
 dNum = 0;
 while(digit(*pc)) dNum = dNum * 10 + (*pc++ - '0');
 if (*pc == '.'){
 ****** divisor = 1, frac = 0;
 while(digit(*pc)){
 divisor *= 0.1;
 frac += (*pc++ - '0') * divisor;
 }
 dNum += frac;
 }
 return true;
 }
 pc = pc0;
 return false;
}
// routine to lex some constant word
bool SeeWord(const char* &pc, const char* sWord){
 ScanWhite(pc);
 const char* pc0 = pc;
 int len = strlen(sWord);
 if (strncmp(pc, sWord, len)==0 && !alphanum(pc[len])){
 pc += len;
 return true;
 }
 pc = pc0;
 return false;
}
// routine to lex a single character like an operator
bool SeeChar(const char* &pc, const char c){
 ScanWhite(pc);
 const char* pc0 = pc;
 if (*pc == c){
 pc++;
 return true;
 }
 pc = pc0;
 return false;
}
// primitive expression parser
void ParsePrimitiveExpr(const char* &pc, CNode* &p){
 ****** dNum;
 char sId[100];
 if (0);
 else if (SeeNum(pc, dNum)){
 p = new CNode(dNum);
 }
 else if (SeeId(pc, sId)){
 // see if its a function call
 if (SeeChar(pc, '(')){
 p = MakeNewFunctionCallNode(sId);
 while(!SeeChar(pc, ')')){
 CNode* p1 = null;
 ParseExpression(pc, p1);
 AddArgumentExprToFunctionCallNode(p, p1);
 SeeChar(pc, ','); /* optional comma separator */
 }
 }
 // otherwise its just a variable reference
 else {
 p = new CNode(sId);
 }
 }
 // handle embedded expressions
 else if (SeeChar(pc, '(')){
 ParseExpression(pc, p);
 if (!SeeChar(pc, ')')) /* deal with syntax error */
 }
}
#define PARSE_HIGHER ParsePrimitiveExpr
// product parser
void ParseProduct(const char* &pc, CNode* &p){
 PARSE_HIGHER(pc, p);
 while(true){
 if (0);
 else if (SeeChar(pc, '*')){
 CNode p1 = null;
 PARSE_HIGHER(pc, p1);
 p = new CNode('*', p, p1);
 }
 else if (SeeChar(pc, '/')){
 CNode p1 = null;
 PARSE_HIGHER(pc, p1);
 p = new CNode('/', p, p1);
 }
 else break;
 }
}
#undef PARSE_HIGHER
#define PARSE_HIGHER ParseProduct
// sum parser
void ParseSum(const char* &pc, CNode* &p){
 PARSE_HIGHER(pc, p);
 while(true){
 if (0);
 else if (SeeChar(pc, '+')){
 CNode p1 = null;
 PARSE_HIGHER(pc, p1);
 p = new CNode('+', p, p1);
 }
 else if (SeeChar(pc, '-')){
 CNode p1 = null;
 PARSE_HIGHER(pc, p1);
 p = new CNode('-', p, p1);
 }
 else break;
 }
}
#undef PARSE_HIGHER
// can insert more routines like the above
// to handle move operators
#define PARSE_HIGHER ParseSum
// overall expression parser
void ParseExpression(const char* &pc, CNode* &p){
 PARSE_HIGHER(pc, p);
}

Добавлен некоторый синтаксис инструкции в стиле Pascal:

void ParseStatement(const char* &pc){
 char sId[100];
 if(0);
 else if (SeeWord(pc, "begin")){
 while(!SeeWord(pc, "end")){
 ParseStatement(pc);
 SeeChar(pc, ';');
 }
 }
 else if (SeeWord(pc, "while")){
 CNode* p1 = null;
 ParseExpression(pc, p1);
 ParseStatement(pc);
 /* semantics for while statement */
 }
 else if (SeeWord(pc, "if")){
 CNode* p1 = null;
 ParseExpression(pc, p1);
 ParseStatement(pc);
 if (SeeWord(pc, "else")){
 ParseStatement(pc);
 }
 /* semantics for if statement */
 }
 else if (SeeWord(pc, "for")){
 /* you do it */
 }
 // handle assignments and subroutine calls
 else if (SeeId(pc, sId)){
 if(0);
 else if (SeeChar(pc, '=')){
 CNode* p1 = null;
 ParseExpression(pc, p1);
 /* semantics for assignment statement */
 }
 else if (SeeChar(pc, '(')){
 CNode* p = MakeNewFunctionCallNode(sId);
 while(!SeeChar(pc, ')')){
 CNode* p1 = null;
 ParseExpression(pc, p1);
 AddArgumentExprToFunctionCallNode(p, p1);
 SeeChar(pc, ','); /* optional comma separator */
 }
 }
 else {
 /* we have a 1-word statement, which is OK in pascal */
 }
 }
 else {
 /* syntax error */
 }
}

Он по-прежнему нуждается в синтаксисе для индексирования массива, объявления переменных и определения функции, но я надеюсь, что это ясно, как это сделать.


В своем классическом тексте программирования "Алгоритмы + структуры данных = программы" Никлаус Вирт разрабатывает полный рекурсивный синтаксический анализатор (в Паскале) для простого языка Pascal0.


Фактически вы можете использовать flex и bison с С++. В этот учебник, например, вы можете видеть, что раздел 5 посвящен этому вопросу. Просто зайдите в Google, и я уверен, что вы найдете много примеров.


Когда вы используете Lex и Yacc, вы на самом деле ничего не пишете в C. Lex - это собственный язык, так как это Yacc. Итак, вы пишете лексический анализатор в Lex и парсере в Yacc. Однако для Pascal входные данные Lex и Yacc уже доступны.

В результате анализатор и лексер имеют C-интерфейсы, это правда. Однако большинство языков, включая С++, имеют простые способы вызова (или переноса) C-интерфейсов.

Я не эксперт в этом, но я уверен, что все выше сказанное касается ANTLR.

Если вы просите сделать это в "чистом С++" (что бы это ни значило), изучите использование boost spirit. Я действительно не вижу смысла в теоретической чистоте, если это придает тонне больше работы.

Написание собственных лексеров и парсеров вручную - это действительно любопытно. Лексер - одна из немногих ситуаций, где вы можете обосновать использование как goto s, так и препроцессора. Однако я бы не предложил его для полномасштабного языка, такого как Паскаль, если вы можете его избежать. Это была бы большая работа. Я говорю человеко-лет.


Если вы пишете его на Java, я бы рекомендовал ANTLR. Это хороший генератор парсеров LL (*), написанный на Java. Там потрясающая книга для Амазонки.


bison и flex являются генераторами канонического синтаксического анализатора. Если вас интересует С++, я нашел boost spirit полезным. Я никогда не использовал его ни для чего сложного, как для компилятора. Я уверен, что у других будут интересные предложения для других языков, таких как С#...


Я написал синтаксический анализатор XSLT с использованием flex и bison. В последнее время я делаю проект с использованием ANTLR:

Является синтаксисом языка JFig эффективным и понятным (и лучше, чем Spring -Frameworks XML DSL)?

Мне нравилось работать в ANTLR гораздо больше, чем Flex и Bison. ANTLR ставит вас на более высокий уровень абстракции в некоторых отношениях. Лексические определения и грамматика парсера могут идти в одном файле. (ANTLR будет генерировать файл токена.)

Одним из ключевых элементов является способность определять древовидные грамматики. В основном вы выполняете грамматический анализ по языку ввода и выполняете действия, которые переписываются на очень оптимальный выход дерева AST (которые остаются в виде связанных структур данных в памяти). Затем вы можете передать это дерево другому парсеру, определенному в отдельном файле парсера дерева. Дерево-парсер - это то, где вы делаете реальную работу необходимых элементов действий.

Это хороший подход, так как вы можете сохранить форму AST и повторно обрабатывать ее по мере необходимости - очищать определенные узлы поддерева для обработки на основе последних действий и т.д. Подумайте о чем-то вроде интерпретатора языка. Вместо того, чтобы переходить в цикл for и обрабатывать язык с нуля снова и снова, он может просто обрабатывать это представление AST.

В моем случае я разработал bean factory для выполнения инъекции зависимостей IoC. Мой bean factory хранит AST в дескрипторе bean во время выполнения. Когда ему нужно создать (или получить) новый экземпляр bean, я просто передаю поддерево DES-описания дескриптора bean в свой синтаксический анализатор дерева - результат - это желаемый экземпляр bean (есть много факторов, которые входят в для определения того, как создать экземпляр запрошенного bean, включая создание любых других beans, на которые ссылаются и/или применение других специальных действий через мета атрибуты).

Наконец, мой текущий bean factory нацелен на Java, но я хочу нацелить ActionScript3 и С#.NET. ANTLR поддерживает это.

Как уже упоминалось, Терренс Парр написал книгу о том, как использовать ANTLR. Он нацелен на работающих программистов, которые должны сделать что-то практическое с ANTLR (в отличие от академического подхода к предмету).


Если ваш желающий С#, соответствующий этому Question, попробуйте Gardens Point GPPG и GPLEX.

licensed under cc by-sa 3.0 with attribution.