VPF::Рекурсивный Синтаксический Анализатор

Schweppes

Дата 19.4.2009, 22:01 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 6
Регистрация: 19.4.2009

Репутация: нет
Всего: нет

Здравствуйте, уважаемые программисты! Обращаюсь к вам за помощью. Третий раз с нуля переписываю программу, и на третий раз совсем не могу придумать рационального решения.

Задача такая:

Построить синтаксический анализатор для понятия текст_со_скобками.

текст_со_скобками::= элемент | элемент текст_со_скобками

элемент::= А | В | (текст_со_скобками) | [текст_со_скобками] | {текст_со_скобками}

Всё это нужно сделать с использованием рекурсии. Никакими массивами пользоваться нельзя. Считывать с входного файла нужно посимвольно.
В выходной файл будет занесена исходная последовательность символов + название ошибки, которая там встретится, если она есть.
В файл протокола заносятся название использованных функций, с глубиной их рекурсивного вызова, тоесть чем вызов глубже, тем отступ больше.

Пример входного файла: (A)(B){A} или [(A)] или [()] -- тут будет ошибка, так как внутри круглых скобок нет символа, программа остановится после закрывающих круглых скобок. В выходном файле должна быть последовательность до ошибки и название самой ошибки. Вот ещё пример: [({A(A)}]) тут ошибка в том, что закрывается квадратная скобка, когда должна закрываться круглая.

Вот мой код:

Код


#include <iostream.h>
#include <fstream.h>

#include <conio.h>

fstream F,P,L;
int bracket();
int square();
int round();
int symbol();
int figure();

char S;
int j=0, k=0, z=0;
int q=0;
int error(int t)
{   
   switch(t)
     {
       case 2: P<<"Nedopystimyi simvol "<<endl;
       break;
       case 3: P<<"Otsutstvuet A/B me}|{dy skobkami"<<endl;
       break;
       case 4: P<<"Net otkrivaushey krugloy skobki";
       break;
       case 5: P<<"Net otkrivaushey figurnoy skobki";
       break;
       case 6: P<<"Net otkrivaushey kvadratnoy skobki";
       break;
       case 7: P<<"Kvadratnie skobki ne zakriti"<<endl;
       break;
       case 8: P<<"Kruglue skobki ne zakriti ";
       break;
       case 9: P<<"Figurnie skobki ne zakriti ";
       break;
       case 10: P<<"Net Otkrivaushih skobok";
       break;


     }
   return 0;
}

void main()
{
  F.open("input1.txt",ios::in);
  P.open("output1.txt",ios::out);
  L.open("protok.txt",ios::out);
  int b;
  F.setf(ios::skipws);
  F>>S;
    if(!F.eof())
     {
       F.seekg(ios::beg);
       b=bracket();
       if(b) P<<"^_^";
     }
    else P<<"pustoi fail";
  F.close(); P.close();L.close();
}

int bracket()
{
  int b,res;
  //F>>S;
  L<<"Bracket_Open"<<endl;
  F.seekg(ios::beg);
  F>>S;
  P<<S<<endl;

     if(S=='[') {z=0; b=square();}
    //else if(S=='(') {z=0; b=round();}
       //else if ((S=='A') || (S=='B')) {b=symbol();}
           else if ((S=='}') || (S==']') || (S==')')) {P<<error(10); }
            else {P<<error(2); return res=0;}


  j--;
  for (k=0; k<=j; k++) {L<<"   ";} L<<"Bracket_Close";
  return res;
}
///////////////////////////////////////////////////////////////////////////////////////////

int square ()
{ 
  
  if (S=='[') {j++; for (k=0; k<=j; k++) {L<<"   ";} L<<"Square_Open"<<endl;}
  if (S==']') {for (k=0; k<=j; k++) {L<<"   ";} L<<"Square_Close"<<endl;j--;}

  if (!F.eof())
  {
   F>>S;

     if (!F.eof())

       {
       P<<S<<endl;
       if (S==']') {square(); return 0;}
       if (S=='[') {square(); j--;}
       }
 
   return 1 ;
  }
}
//////////////////////////////////////////////////////////////////////////////////////////////
int round ()
{

}
/////////////////////////////////////////////////////////////////////////////////////////////
int figure ()
{

}
/////////////////////////////////////////////////////////////////////////////////////////////
int symbol ()
{

}

Собственно вопрос. Как сделать функцию для круглых и фигурных скобок + проверка на некорректность, чтобы отслеживалась такая ошибка: {[(A)}] - скобки закрыты неправильно. Или хотя бы ((А))) - нет круглой открывающей.

Если у кого то будет время - посмотрите пожалуйста. Заранее благодарен.

Anikmar

Дата 19.4.2009, 22:29 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2513
Регистрация: 26.11.2006
Где: Санкт-Петербург

Репутация: 5
Всего: 59

А просто A без скобок или AA или AB допустимо?

Schweppes

Дата 19.4.2009, 22:57 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 6
Регистрация: 19.4.2009

Репутация: нет
Всего: нет

Anikmar, просто А может быть; подряд идущих АА или АB может быть сколько угодно.
Если удастся, то можно реализовать ещё такую некорректную ситуацию: ((А)А) - ошибка, так как вторая А стоит между скобками, но в тоже время (A(A)) является правильной последовательностью.

Вот ещё разные примерчики:
)(A){AA} - программа должна остановиться после первого символа и вывести в выходной файл ошибку, что нет открывающей круглой скобки.
А(А) - правильно
А(А(А) - ошибка, так как нет закрывающей круглой скобки
А({A)} - ошибка, так как фигурные или круглые скобки закрыты непрально.

Это сообщение отредактировал(а) Schweppes - 19.4.2009, 22:58

Anikmar

Дата 19.4.2009, 23:29 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2513
Регистрация: 26.11.2006
Где: Санкт-Петербург

Репутация: 5
Всего: 59

А рекурсия необходима? Без нее мне кажется проще.

Schweppes

Дата 19.4.2009, 23:45 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 6
Регистрация: 19.4.2009

Репутация: нет
Всего: нет

Anikmar, Тема рекурсии, так что использовать можно только её....И никаких массивов)

kamre

Дата 20.4.2009, 03:50 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 330
Регистрация: 24.3.2006

Репутация: 2
Всего: 13

Цитата(Schweppes @ 19.4.2009, 22:57)

Если удастся, то можно реализовать ещё такую некорректную ситуацию: ((А)А) - ошибка, так как вторая А стоит между скобками, но в тоже время (A(A)) является правильной последовательностью.

А почему это вдруг "((A)A)" считается ошибкой?
S => E => (S) => (E S) => ((S) S) => ((E) S) => ((A) S) => ((A) E) => ((A) A)

У меня пока вот так получается в коде на C++:

Код


#include <iostream>

#include <boost/spirit/core.hpp>
#include <boost/spirit/error_handling/exceptions.hpp>

using namespace boost::spirit;
using namespace std;

enum parse_error {
  element_expected,
  rparen_expected,
  rbrace_expected,
  rbracket_expected
};

inline const char* parse_error_msg(const parse_error error) {
  static const char* msg[] = {
      "expected A, B, (, { or [",
      "expected )",
      "expected }",
      "expected ]"
  };
  return msg[error];
}

typedef assertion<parse_error> parse_assertion;

const parse_assertion expect_element(element_expected);
const parse_assertion expect_rparen(rparen_expected);
const parse_assertion expect_rbrace(rbrace_expected);
const parse_assertion expect_rbracket(rbracket_expected);

struct error_handler {
  template <typename ScannerT, typename ErrorT>
  error_status<> operator()(const ScannerT & scan,
                            const ErrorT & err) const {
    cerr << "error: " << parse_error_msg(err.descriptor)
         << " after \"" << string(scan.first, err.where) << "\"" << endl;
    return error_status<>(error_status<>::fail);
  }
};

struct expr_grammar: public grammar<expr_grammar> {
  template <typename ScannerT> class definition {
    public:
    definition(expr_grammar const & self) {
      guard<parse_error> g;
      gexpr   = g(expr >> end_p)[error_handler()];
      expr    = expect_element(+element);
      element = ch_p('A') | ch_p('B') | paren | brace | bracket;
      paren   = ch_p('(') >> expr >> expect_rparen(ch_p(')'));
      brace   = ch_p('{') >> expr >> expect_rbrace(ch_p('}'));
      bracket = ch_p('[') >> expr >> expect_rbracket(ch_p(']'));
    }
    rule<ScannerT> const & start() const {
      return gexpr;
    }
    private:
      rule<ScannerT> gexpr, expr, element, paren, brace, bracket;
  };
};

void parse_text(const char * str) {
  cout << "parsing text: \"" << str << "\"  ";
  if (parse(str, expr_grammar(), space_p).full)
    cout << "ok" << endl;
}

int main() {
  parse_text("A");
  parse_text("ABBA");
  parse_text("(A)");
  parse_text("[(A)]");
  parse_text("(A)(B){A}");
  parse_text("[()]");
  parse_text("{A(A)}");
  parse_text("[({A(A)}])");
  parse_text("((A)A)");
  parse_text("(A(A))");
  parse_text(")(A){AA}");
  parse_text("A(A(A)");
  parse_text("A({A)}");
  return EXIT_SUCCESS;
}

Цитата

parsing text: "A"  ok
parsing text: "ABBA"  ok
parsing text: "(A)"  ok
parsing text: "[(A)]"  ok
parsing text: "(A)(B){A}"  ok
parsing text: "[()]"  error: expected A, B, (, { or [ after "[("
parsing text: "{A(A)}"  ok
parsing text: "[({A(A)}])"  error: expected ) after "[({A(A)}"
parsing text: "((A)A)"  ok
parsing text: "(A(A))"  ok
parsing text: ")(A){AA}"  error: expected A, B, (, { or [ after ""
parsing text: "A(A(A)"  error: expected ) after "A(A(A)"
parsing text: "A({A)}"  error: expected } after "A({A"

Schweppes

Дата 20.4.2009, 07:42 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 6
Регистрация: 19.4.2009

Репутация: нет
Всего: нет

kamre, У вас используется структура? к сожалению её применять нельзя. Только Обычные сравнения при помощи рекурсий, как я начал делать...

zim22

Дата 20.4.2009, 08:03 (ссылка)

(голосов:1)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 29
Всего: 69

Цитата(Schweppes @ 20.4.2009, 07:42

)

структура? к сожалению её применять нельзя

структуру нельзя, а буст можно?

Код


#include <boost/spirit/core.hpp>
#include <boost/spirit/error_handling/exceptions.hpp>

--------------------

C++ FAQ Lite

xvr

Дата 20.4.2009, 12:37 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 35
Всего: 223

Цитата(Schweppes @ 20.4.2009, 07:42)

kamre, У вас используется структура?

У него используется готовый парсер (boost/spirit) smile

Вам нужен 'метод рекурсивного спуска' - ищите
Или скормите вашу граматику ANTLR - он вам выдаст готовый парсер, сделанный по этой технологии

Schweppes

Дата 20.4.2009, 16:57 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 6
Регистрация: 19.4.2009

Репутация: нет
Всего: нет

zim22,
xvr, Ни бустов, ни парсеров нельзя. Надо делать в лоб)

xvr

Дата 20.4.2009, 17:15 (ссылка)

(голосов:1)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 35
Всего: 223

Цитата(Schweppes @ 20.4.2009, 16:57)

zim22,
xvr, Ни бустов, ни парсеров нельзя. Надо делать в лоб)

ANTLR и построит 'в лоб'. Правда не уверен, что программа, которую он сгенерит, будет похожа на написанную вручную smile

В общем, метод рекурсивного спуска реализуется так:
1) Строим грамматику - 1 правило на каждый вариант:

Код


текст_со_скобками ::= элемент 
текст_со_скобками ::=  элемент текст_со_скобками
элемент::= А
элемент::= В
элемент::= (текст_со_скобками)
элемент::= [текст_со_скобками]
элемент::= {текст_со_скобками}

2) На каждое правило делаем функцию, которая его отрабатывает.
Функции строятся так:
а) Есть 1 lookahead символ, по нему определяем, какую функцию звать
б) Когда функция обработает этот lookahead, она читает следующий символ (и т.д.)

Код


char lookahead;
istream inp;

int get_sym()
{
 if (!lookahead) inp>>lookahead;
 return inp.eof()?-1:lookahead;
}

void consume() {lookahead=0;}

void expect(char sym) 
{
 if (get_sym()==sym) consume();
 else error();
}

// Syntax processing

void text_with_brackets()
{
 element();
 if (get_sym()!=-1) text_with_brackets();
}

void element()
{
 int sym=get_sym(); consume();
 switch(sym)
  {
    case 'A': break;
    case 'B': break;
    case '[':  text_with_brackets(); expect(']'); break;
    case '(':  text_with_brackets(); expect(')'); break;
    case '{':  text_with_brackets(); expect('}'); break;
    default: error();
  }
}


main()
{
 ...
 text_with_brackets();
 ...
}

Протоколирование и пр. добавить по вкусу smile

Anikmar

Дата 20.4.2009, 19:23 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2513
Регистрация: 26.11.2006
Где: Санкт-Петербург

Репутация: 5
Всего: 59

Мой вариант.
На все возхможные приколы не тестировал - но вроде основное отрабатывает.

Код


//---------------------------------------------------------------------------
#include <conio>
#include <iostream>
#include <fstream.h>
#pragma hdrstop

#include <tchar.h>
//---------------------------------------------------------------------------
#pragma argsused

using namespace std;
fstream InputFile;
fstream OutputFile;
fstream ProtocolFile;

bool FindCloseBracket(int pRecoursingNumber,char pSymbol)
{
    char CurSymbol,LastSymbol;
    bool Result = true;
    bool FlagWrongSymb = false;

    for (int i=1;i<=pRecoursingNumber;++i) ProtocolFile << " ";
    ProtocolFile << "FindCloseBracket # " << pRecoursingNumber << endl;


    while(Result)
    {
        InputFile >> CurSymbol;
        if (InputFile.eof()) break;
        OutputFile << CurSymbol;
        switch (CurSymbol)
        {
            case 'A':
            case 'B':
                if (FlagWrongSymb) { Result = false; break; }
                continue;
            case '(':
            case '[':
            case '{':
                FlagWrongSymb = false;
                if (!FindCloseBracket(pRecoursingNumber+1,CurSymbol)) return false;
                if (pSymbol != 0) FlagWrongSymb = true;
                continue;
            case ')':
                if (pSymbol != '(') Result = false;
                else return true;
            case ']':
                if (pSymbol != '[') Result = false;
                else return true;
            case '}':
                if (pSymbol != '{') Result = false;
                else return true;
        }
    }

    if (pSymbol != 0) Result = false;

    if (!Result)
    {
        if (FlagWrongSymb)
        {
            OutputFile << " Error: " << CurSymbol << " after close bracket " << endl;
            return Result;
        }
        switch (pSymbol)
        {
            case '(': OutputFile << " Error: ) required" << endl;    break;
            case '[': OutputFile << " Error: ] required" << endl;    break;
            case '{': OutputFile << " Error: } required" << endl;    break;
            default:
                OutputFile << " Error: Ilegal symbol " << CurSymbol << endl;
        }

    }
    return Result;
}

int _tmain(int argc, _TCHAR* argv[])
{
    InputFile.open("input.txt",ios::in);
    OutputFile.open("output.txt",ios::out);
    ProtocolFile.open("protocol.txt",ios::out);
    if (FindCloseBracket(1,0)) cout << "Errors not found" << endl;
    else cout << "End of work with error(s)" << endl;
    InputFile.close();
    OutputFile.close();
    ProtocolFile.close();
    getch();
    return 0;
}

cupper

Дата 20.4.2009, 21:01 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 525
Регистрация: 29.11.2006

Репутация: нет
Всего: 1

ватсон все элементарно, небуду писать код потомучто его будет много да и отлаживать пришлосьбы опишу логику как вы должны делать.

Создать следующие функции:
Функция которая вызываеться если попалась открывающаяся круглая скобка ( (назовем ее "функция_(" )
Функция которая вызываеться если попалась открывающаяся фигурная скобка { ( (назовем ее "функция_{" )
Функция которая вызываеться если попалась открывающаяся квадратная скобка [ ( (назовем ее "функция_[" )
... аналогичный функции для всех остальных видов открывающихся функций

Далее что эти функции должны делать, распишу на примере одной, все остальный аналогичны, разницы только в видах скобок
функция_( делает следующее:
1) считывает следующих за ней символ (если функция вызываеться сразу для следующего за ( символом то ненадо ничего считывать)
2) смотрим что это за символ:
--2.1) если это ( то рекурсивно вызываем функция_( либо на этом символе лобо на символе следующим за этим (тут вы сами вольны выбрать логику програмы, и советую придерживаться выбранной, проще отслеживать алгоритм будет)
-------- если это { то вызываем функция_{ либо на этом символе лобо на символе следующим за этим
-------- и так проверка на все виды скобок
-------- если это символ отличтный от допустимых открывающихся скобок то проверяем на его допустимость как символа A, B и т.д.
-------- если это не допустимый символ (может быть закрывающаяся скобка или что либо иное) говорим RETURN ERROR
--------2.1.1) сюда попадаем если считаный символ был удовлитворительной буквой (A, B и т.д.)
--------------- считываем следующим за ним символ
--------------- если это ( то рекурсивно вызываем функция_(
--------------- если это { то вызываем функция_{
--------------- и так проверка на все виды скобок
--------------- если это не скобка, проверяем являетьсяли символ допустимым A, B, и т.д. Если да то возвращаемся на 2.1.1
Если нет выходим из цыкла (на этом символе который не открывающаяся скобка и не допустимая буква)
-------- Проверяем являетьсяли этот символ закрывающийся круглой скобкой ( (для функции функция_{ что это символ } и тогдалее для всех функций и соотвествующих им закрывающихся скобок)
-------- Если да тогда благополучно выходим из это функции
-------- если нет ГОВОРИМ RETURN ERROR (и собсно этот символ и есть первая ошибка)

Это сообщение отредактировал(а) cupper - 20.4.2009, 21:08

baldina

Дата 21.4.2009, 14:50 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 15
Всего: 101

Читайте xvr, у него наиболее приятный и осмысленный код, удовлетворяющий заданию.

Добавлено через 3 минуты и 43 секунды
xvr, lookahead неплохо бы начально проинициализировать нулем. для понятности smile

Anikmar

Дата 21.4.2009, 21:53 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2513
Регистрация: 26.11.2006
Где: Санкт-Петербург

Репутация: 5
Всего: 59

Цитата(baldina @ 21.4.2009, 14:50

)

Читайте xvr, у него наиболее приятный и осмысленный код, удовлетворяющий заданию.

Что-то он у меня не запустился :(

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »