Разработка простого парсера
https://stackoverflow.com/questions/391432
-
23-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
В мою повседневную работу входит разработка компилятора, подобного Паскалю.Я все время работал над оптимизацией и генерацией кода.
Я также хотел бы начать учиться создавать простой парсер для того же языка.Однако я не совсем уверен, как это сделать.Флекс и Бизон кажутся лучшим выбором.Но разве нельзя написать парсер на C++ или C#?Я немного пугаюсь с C.
Yacc++ поддерживает C#, но он лицензирован.Я ищу всю помощь, которую могу найти в этом отношении.Предложения будут высоко оценены.
Решение
Я считаю, что вы можете использовать ANTLR с C#.Я никогда не пробовал это сам (пока), однако есть учебник здесь это может указать вам в правильном направлении.
Другие советы
Лично я накатываю свой лексер и парсер (LL).Вот очень сокращенный пример.Он написан на C++, но, надеюсь, вы сможете его адаптировать.Он использует макрос 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, double &dNum){
ScanWhite(pc);
const char* pc0 = pc;
if (digit(*pc)){
dNum = 0;
while(digit(*pc)) dNum = dNum * 10 + (*pc++ - '0');
if (*pc == '.'){
double 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){
double 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);
}
Добавлен синтаксис операторов в стиле Паскаля:
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 */
}
}
Ему по-прежнему нужен синтаксис для индексации массивов, объявления переменных и определения функций, но я надеюсь, что теперь понятно, как это сделать.
В своем классическом тексте по программированию Алгоритмы + Структуры данных = Программы, Никлаус Вирт разрабатывает полный анализатор рекурсивного спуска (на языке Pascal) для простого языка, подобного Pascal0.
Если бы вы писали это на Java, я бы рекомендовал ANTLR.Это хороший генератор синтаксического анализатора LL(*), написанный на Java.На Amazon тоже есть потрясающая книга.
bison & flex — канонические генераторы парсеров.Если вас интересует C++, я нашел поднять дух полезный.Однако я никогда не использовал его для чего-то столь сложного, как компилятор.Я уверен, что у других будут интересные предложения по другим языкам, таким как C#...
На самом деле вы можете использовать flex & bison с C++.В этот урок, Например, вы можете видеть, что этому вопросу посвящен раздел 5.Просто поищите в Google, и я уверен, вы найдете множество примеров.
Я написал парсер XSLT с использованием flex и bison.Однако позже я делаю проект с использованием ANTLR:
Является ли синтаксис языка Jfig эффективным и понятным (и лучше, чем XML DSL Spring-Framework)?
Мне понравилось работать в ANTLR гораздо больше, чем во Flex и Bison.ANTLR в некоторых отношениях поднимает вас на более высокий уровень абстракции.Лексические определения и грамматика синтаксического анализатора могут находиться в одном файле.(ANTLR сгенерирует файл токена.)
Одним из ключевых элементов является возможность определять древовидные грамматики.По сути, вы выполняете грамматический анализ входного языка и выполняете действия, которые перезаписывают в высокооптимальное выходное дерево AST (которые остаются в памяти в виде связанных структур данных).Затем вы можете передать это дерево другому синтаксическому анализатору, определенному в отдельном файле синтаксического анализатора дерева.Анализатор дерева — это место, где вы выполняете реальную работу над нужными вам элементами действий.
Это хороший подход, поскольку вы можете сохранить форму AST и повторно обрабатывать ее по мере необходимости - отделяя определенные узлы поддерева для обработки на основе последних действий и т. д.Подумайте о чем-то вроде языкового переводчика.Вместо того, чтобы входить в цикл for и снова и снова обрабатывать язык с нуля, можно просто обрабатывать его представление AST.
В моем случае я разработал фабрику компонентов для внедрения зависимостей IoC.Моя фабрика компонентов сохраняет AST дескриптора компонента во время выполнения.Когда необходимо создать (или получить) новый экземпляр компонента, я просто передаю поддерево AST дескриптора компонента моему анализатору дерева - результатом является желаемый экземпляр компонента (существует множество факторов, влияющих на определение способа создания экземпляра компонента). запрошенный bean-компонент, включая создание любых других bean-компонентов, на которые имеются ссылки, и/или применение другого специального поведения через метаатрибуты).
Наконец, моя текущая фабрика компонентов ориентирована на Java, но я хочу использовать ActionScript3 и C# .NET.У ANTLR есть поддержка для этого.
Как уже упоминалось, Терренс Парр написал книгу о том, как использовать ANTLR.Он предназначен для работающих программистов, которым необходимо сделать что-то практическое с ANTLR (в отличие от академической трактовки предмета).
Если вам нужен C# согласно этому Вопрос попробуйте Gardens Point GPPG и GPLEX.
Когда вы используете Lex и Yacc, вы практически ничего не пишете на C. Лекс это собственный язык, как и Yacc.Итак, вы пишете лексический анализатор на Lex, а синтаксический анализатор на Якк.Однако для Pascal входные данные Lex и Yacc уже доступен.
Получающиеся парсер и лексер имеют интерфейсы C, это правда.Однако большинство языков, включая C++, имеют простые способы вызова (или переноса) интерфейсов C.
Я не эксперт в этом, но уверен, что все вышесказанное относится и к ANTLR.
Если вы просите сделать это на «чистом C++» (что бы это ни значило), изучите возможность использования boost дух.Хотя я не вижу смысла в теоретической чистоте, если это потребует еще больше работы.
Написание собственных лексеров и парсеров вручную — это действительно весело.Лексер — одна из немногих ситуаций, когда можно оправдать использование обоих идти кs и препроцессор.Однако я бы не советовал использовать его для полноценного языка, такого как Паскаль, если вы можете этого избежать.Это потребует много работы.Я говорю о человеко-летах.
