Есть ли простой способ токенизировать строку без полноценного лексера?

Я пытаюсь реализовать алгоритм маневровой станции, но мне нужна помощь в определении как лучше всего разделить строку на ее токены.

Если вы заметили, первым шагом алгоритма является «чтение токена». Это не совсем нетривиальная вещь. Токены могут состоять из чисел, операторов и скобок.

Если вы делаете что-то вроде:

(5+1)

Простой string.split() даст мне массив токенов { "(", "5", "+", "1", ")" }.

Однако это становится более сложным, если у вас есть числа с несколькими цифрами, например:

((2048*124) + 42)

Теперь наивный string.split() не поможет. Многозначные числа - это проблема.

Я знаю, что мог бы написать лексер, но есть ли способ сделать это без написания полноценного лексера?

Я реализую это в JavaScript, и мне бы хотелось, если это возможно, не идти по пути лексера. Я буду использовать операторы «*», «+», «-» и «/» вместе с целыми числами.


javascript tokenize computer-science lexer shunting-yard
person KingNestor    schedule 19.10.2009    source источник
comment
Все, что правильно преобразует поток символов в поток токенов, является лексером.   -  person Steve S    schedule 20.10.2009

Ответы (2)


arrow_upward
6
arrow_downward

Как насчет регулярных выражений? Вы можете легко написать регулярное выражение, чтобы разделить его так, как хотите, и метод JS string.split также принимает регулярное выражение в качестве параметра.

Например... (измените, чтобы включить все необходимые символы и т. д.)

/([0-9]+|[*+-\/()])/
person Jani Hartikainen    schedule 19.10.2009
comment
+1 Он ломается из-за вложенных скобок, таких как '((42 + 7) * 4)', но это можно исправить, добавив скобки во вторую половину выражения: /([0-9]+|[*+-\/()])/ - person brianpeiris; 19.10.2009
comment
Он по-прежнему использует алгоритм, указанный на вики-странице. Псевдокод говорит «Прочитать токен». - person mmcdole; 19.10.2009
comment
@Simucal, @KingNestor Теперь я в замешательстве, разве это не правильный ответ? - person brianpeiris; 19.10.2009
comment
Некоторые люди, столкнувшись с проблемой, думают, что я знаю, что буду использовать регулярные выражения. Теперь у них две проблемы. codinghorror.com/blog/archives/001016. html - person OscarRyz; 19.10.2009
comment
@brianpeiris, О, я не говорю, что это не ответ. Я просто комментировал первую строку ответа Яни, если вы не хотите писать алгоритм, указанный в вики. Алгоритм не указывает, как читать токен, он просто говорит о том, что прочитать токен. Таким образом, KingNestor следует алгоритму, используя этот ответ. - person mmcdole; 19.10.2009
comment
Извините, если я что-то упустил, но не могли бы вы использовать совпадение, а не разделение, в этом регулярном выражении? например результат = subject.match(/([0-9]+|[*+-\/()])/img); - person Andre Artus; 08.06.2010

arrow_upward
2
arrow_downward

Вы можете использовать глобальное соответствие, как описано на странице http://mikesamuel.blogspot.com/2009/05/efficient-parsing-in-javascript.html

По сути, вы создаете одно регулярное выражение, описывающее токен.

/[0-9]+|false|true|\(|\)/g

и поместите «g» в конец, чтобы он соответствовал глобально, а затем вы вызываете его метод сопоставления

var tokens = myRegex.match(inputString);

и вернуть массив.

person Mike Samuel    schedule 20.10.2009
comment
Я думаю, что это лучший метод. Я использую result = subject.match(/(-?[0-9]+|[*+-\/()])/g); Вы получаете токены, которые вам нужны, и токены, которые вы хотите :). - person Andre Artus; 08.06.2010