Re: коммивояжёр

From

Vitaly Lugovsky (2:5080/1003)

To

Alexey Krasnov

Date

2003-01-14T18:04:59Z

Area

RU.ALGORITHMS

From: Vitaly Lugovsky <vsl@ontil.ihep.su>

Alexey Krasnov <Alexey.Krasnov@p96.f196.n5066.z2.fidonet.org> wrote:

> OK> Например - разбор и вычисление арифметического выражения со
> OK> скобками и с приоритетами операций.
> 
> yacc-like парсеры вовсе нерекурсивны.

 Так то детский сад, штаны на лямках. А слабО придумать без хотя бы
комбинаторов аналог таких вот парсеров:
http://www.cs.uu.nl/groups/ST/Software/UU_Parsing/
http://www.ki.informatik.uni-frankfurt.de/~klose/lucky.html
http://www.cs.ruu.nl/~daan/parsec.html
 
 Ну и самый навороченный:

http://www.cse.unsw.edu.au/~chak/haskell/ctk/

> Не думаю, что используемые в серьезных
> компиляторах парсеры делаются рекурсивно,

 Зря. Думать - полезно.

> т.к. для объемных грамматик
> количество ветвлений алгоритма возрастает с ужасающей быстротой. Гораздо
> выгоднее делать разбор по сгенеренным таблицам нерекурсивным алгоритмом.

 Но это только для примитивных грамматик. А если грамматика меняется
динамически - что делать бум?

--- ifmail v.2.15dev5
 * Origin: (http://news.cca.usart.ru/) USURT's FidoNET<-> (2:5080/1003@fidonet)