Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Дерево if-then-else-case

Автор: Teresh 2.12.2010, 00:57

Добрый день. НУжно постоить дерево конструкций if-then-else-case языка Pascal. Мой алгоритм такой: из текста выдираю if-then-else-case регулярным выражением, а дальше начинаются проблемы Например if   then     if       then else не получается отнести последний else к первому if может кто сталкивался с данной проблемой и может помочь?

Автор: ksnk 2.12.2010, 01:09

Цитата(Teresh @  2.12.2010,  00:57 ) не получается отнести последний else к первому if потому что не хватает begin-end'ов. без них в этом примере else и в самом деле будет относится к внутреннему блоку Добавлено через 2 минуты и 12 секунд А рекурсивному спуску вас там, случайно не учили? Достаточно универсальный и простой в реализации метод парсинга. Для паскаля, во всяком случае, подходит.

Автор: Teresh 2.12.2010, 01:30

нет, с рекурсивным списком не знаком программу пишу на C# может там есть какие-то возможности для задания моего?

Автор: ksnk 2.12.2010, 02:12

Цитата(Teresh @  2.12.2010,  01:30 ) с рекурсивным списком не знаком Рекурсивный спУск. Recursive descent parser, если по буржуински. Проще погуглить и поискать примеры реализации какой-то несложной грамматики на каком-нибудь знакомом языке программирования, тогда его простота будет очевиднее. Обычно встречается заумное математическое описание, которое у недостаточно преосвященного человека может вызвать только отвращение    Можно стековой машинкой парсить. Это, возможно, проще в смысле понимания механизма действия... А какие еще конструкции в языке предполагаются? Весь паскаль или только урезанный набор конструкций? Если урезанный, возможно и регулярками можно обойтись...

Автор: Teresh 2.12.2010, 07:25

парсить нужно только конструкции if-then-else-case

Автор: ksnk 2.12.2010, 09:24

Teresh, в Паскале есть конструкция  Цитата if условие then оператор 1 else оператор 2; что такое слово case?  Цитата case выражение of     вариант : оператор;     ...     вариант : оператор;     else оператор end; Это ? Без скобок begin-end различать вложенные if'ы нельзя. Они есть?

Автор: Teresh 2.12.2010, 09:57

да, case этот в условии begin-end опционально, но раз без них не работает, то сделаю как обязательное условие

Автор: Akina 2.12.2010, 11:48

Цитата(Teresh @  2.12.2010,  10:57 ) раз без них не работает Работает, если блок состоит из одного оператора. Если больше - наличие begin-end является обязательным.

Автор: ksnk 2.12.2010, 13:08

Если про рекурсивный спуск, то -- нужна разбивка входящего потока по токенам. Токенами будут служебные слова (if|then|else|case|of|begin|end), символы : и ; и финальная . для пущего эффекта. Все остальное будем называть литералами. Разумно выковыривать токены из входящего потока регулярками, хотя иногда эффективнее (с++ и ниже) писать конечный автомат. -- функция getNext() будет выдавать нам следующий токен из потока -- функция goBack() сделает так, чтобы getNext выдал опять тот-же токен, что и в прошлый раз -- текст программы - последовательность операторов, разделенная ; оканчивающаяся точкой.  Цитата function getProgram(){   getSentenses() ;   if(getNext()!='.'){      error('point required as finishing simbol');   } } function getSentenses(){   do{     getOpeator();  } while(getNext()==';');  goBack(); } Оператор - это либо if, либо case, либо begin-end, либо литералы. Определяется по начальному токену. Цитата function getOperator(){   switch(getNext()){     case 'if' :  getIfSentence();break;     case 'case' : getSwitchSentence();break;     case 'begin' : getBeginEndSentence(); break;     case 'else' :      case 'end' :      case 'of' :     case ';' :     case ':' :     case '.' :          goBack();          break;     default:        getLiterals();   } } Конструкция Begin-end - последовательность операторов. заканчивающаяся словоv end Цитата function getBeginEndSentence(){   getSentenses();   if(getNext()!='end')  error('waiting for end '); } Конструкция if-then-else  Цитата function getIfSentence(){   getOperator(); // получили условие   if(getNext()!='then')  error('waiting for then statment ');   getOperator(); // получили оператор then   if(getNext()!='else')  {     goBack();   } else {     getOperator(); // получили оператор else   } } Ну и так далее. Все получается довольно компактно, рекурсивно и обозримо, стоит только приноровится   Конечно, это пока не парсер, а синтаксический чеккер. Чтобы получить дерево парсинга - в нужные места этих функций нужно вставить заполнение веточек этого самого дерева.

Автор: Teresh 2.12.2010, 15:29

Спасибо, вроде разобрался. На самом деле всё довольно просто и понятно.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)