Разбор s-выражений в Go

Вот ссылка на lis.py, если вы не знакомы: http://norvig.com/lispy.html

Я пытаюсь реализовать крошечный интерпретатор lisp в Go. Меня вдохновила реализация lisp Lis.py Питера Норвига на Python.

Моя проблема в том, что я не могу придумать ни одного эффективного способа анализа s-выражений. Я думал о счетчике, который будет увеличиваться на 1, когда он увидит "(" и будет уменьшаться, когда увидит ")". Таким образом, когда счетчик равен 0, вы знаете, что у вас есть полное выражение.

Но проблема в том, что это означает, что вам придется зацикливаться на каждом отдельном выражении, что сделает интерпретатор невероятно медленным для любой большой программы.

Любые альтернативные идеи были бы замечательными, потому что я не могу придумать лучшего способа.


go lisp interpreter s-expression
person Francis    schedule 08.07.2015    source источник
comment
На самом деле это проблема синтаксического анализа, а не шепелявости. Пример s-выражений может помочь ответить.   -  person nouney    schedule 09.07.2015
comment
Счетчик не сработает. Как и в случае с lis.py, вам нужно использовать стек или рекурсию для разбора кода на минусы и символы.   -  person Sylwester    schedule 09.07.2015

Ответы (2)


arrow_upward
1
arrow_downward

В коде Go at Rosetta реализован парсер S-выражений:

парсер S-выражений в Go

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

person soegaard    schedule 09.07.2015

arrow_upward
1
arrow_downward

Вам, вероятно, понадобится интерфейс «Sexpr» и убедитесь, что ваши структуры данных символов и списков соответствуют интерфейсу. Затем вы можете использовать тот факт, что S-выражение — это просто «один символ» или «список S-выражений».

То есть, если первым символом является "(", это не символ, а список, поэтому начните накапливать []Sexpr, читая каждое содержащееся Sexpr за раз, пока не нажмете ")" во входном потоке. Терминал ")" уже будет использован в любом содержащемся списке.

Если это не "(", вы читаете символ, поэтому читайте, пока не наткнетесь на символ, не входящий в состав символа, отмените его использование и верните символ.

person Vatine    schedule 10.07.2015