![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
juan_gandhi1. Is it true that transforming a word in a context-free language into an AST takes linear time and finite space (except for the growing AST), so it could be done by an FSM? If so, all the stack requirements are about evaluating the trees...
2. Say, I have a language for some kind of expressions, and I want to use the fact that operations are associative (or maybe even commutative); is there a way to stipulate it somehow; or, rather, does it give us something that can be used to facilitate compilation? I wonder...
2. Say, I have a language for some kind of expressions, and I want to use the fact that operations are associative (or maybe even commutative); is there a way to stipulate it somehow; or, rather, does it give us something that can be used to facilitate compilation? I wonder...
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2014-06-23 06:41 am (UTC)no subject
Date: 2014-06-23 06:58 am (UTC)На практике, впрочем, парсятся не вообще CF-языки, а такое их подмножество, которое позволяет построит детерминированный парсер при условии, что можно подглядеть следующий токен (или несколько следующих токенов). То есть парсер по эффективности не отличается от КА (но стек ему все равно нужен). В этом смысле, наверное, можно сказать, что да, для разбора требуется линейное время и конечная память, не считая AST.
2. В SQL такое широко используется для оптимизации запроса; насчет остальных языков затруднюсь сказать. В принципе, там будет дерево, в узле оператор, в потомках операнды; ассоциативность и коммутативность означают, что одну структуру можно заменить другой эквивалентной, и если можно оценить эффективность разных вариантов, то можно подобрать оптимальный. Но это для оптимизации; для собственно компиляции это, наверное, безразлично.
no subject
Date: 2014-06-23 02:33 pm (UTC)Похоже на суперкомпиляцию через эквивалентность.
no subject
Date: 2014-06-23 07:00 am (UTC)It depends on parsing algorithm. "takes linear time and finite space" - definitely not true, as some parsing methods may have exponential complexity. Packrat parsing (a way to implement PEG) can handle everything in linear time but still uses stack. PEG is like CFG minus ambiguity. For arbitrary CFG (with ambiguities that should be parsed and reflected in AST) there is Earley parsing:
"The Earley parser executes in cubic time in the general case {O}(n^3), where n is the length of the parsed string, quadratic time for unambiguous grammars {O}(n^2), and linear time for almost all LR(k) grammars."
Without stack, using just FSM, you're limited to regular grammars, I guess.
no subject
Date: 2014-06-23 07:08 am (UTC)no subject
Date: 2014-06-23 02:29 pm (UTC)no subject
Date: 2014-06-23 02:32 pm (UTC)Правда, я так с ходу не скажу, какой алгоритм так модифицировать легче всего.
На первый взгляд кажется, что PEG, но не факт.
no subject
Date: 2014-06-23 11:15 am (UTC)no subject
Date: 2014-06-23 02:32 pm (UTC)no subject
Date: 2014-06-23 03:11 pm (UTC)no subject
Date: 2014-06-23 03:21 pm (UTC)no subject
Date: 2014-06-23 03:23 pm (UTC)no subject
Date: 2014-06-23 04:12 pm (UTC)no subject
Date: 2014-06-23 04:39 pm (UTC)no subject
Date: 2014-06-23 05:01 pm (UTC)На основании каких данных это утверждение распространяется на остальных женщин? ;)
женский разум
Date: 2014-06-23 05:16 pm (UTC)Re: женский разум
Date: 2014-06-23 05:24 pm (UTC)Re: женский разум
Date: 2014-06-23 05:29 pm (UTC)Re: женский разум
Date: 2014-06-23 06:15 pm (UTC)Из того, что я выучил какой-то язык, не следуюет, что женский мозг непредсказуем.
Re: женский разум
Date: 2014-06-23 06:23 pm (UTC)Математики утверждают, что женский ум предсказуем. Смело.
Ну предскажите чо нить про женщин.
Re: женский разум
Date: 2014-06-23 07:03 pm (UTC)Вы ошибаетесь, я этого не утверждал.
Re: женский разум
Date: 2014-06-23 07:13 pm (UTC)Re: женский разум
Date: 2014-06-23 07:22 pm (UTC)Re: женский разум
Date: 2014-06-23 07:34 pm (UTC)Мой вопрос в том, как же работает мозг, как работает "синаксический анализатор" мозга, как стейт-машина или с бесконечным стеком? Или ни так, ни так, а как же? Или вы не хотите ничего утверждать?
Re: женский разум
Date: 2014-06-23 07:41 pm (UTC)Это утверждение не имеет смысла. Хотя я полагаю, что имелось в виду "анализатор контекстно-свободной грамматики".
> стейт-машина или с бесконечным стеком?
А это, к тому же, ложный выбор, потому что естественные языки не являются ни контекстно-свободными, ни регулярными.
> вы не хотите ничего утверждать?
Я утверждаю, что между синтаксическими анализаторами женского и мужского мозга носителей одного и того же языка нет существенной разницы (она меньше, чем, например, между синтаксическим анализатором носителя флективного языка и изолирующего языка)
Re: женский разум
Date: 2014-06-23 07:57 pm (UTC)Вот например, моя собачка понимает меня в 99% случаев, но по русски не говорит. Я её понимаю хуже.
Re: женский разум
Date: 2014-06-23 08:04 pm (UTC)Напомню, что для получения сколько-нибудь достоверных результатов эксперимент необходимо повторить хотя бы 25 раз, причем с разными экспериментаторами и породами собак.
Re: женский разум
Date: 2014-06-23 08:10 pm (UTC)Re: женский разум
Date: 2014-06-23 08:34 pm (UTC)Я предпочитаю познавать мир научным методом.
> Вы далеко пойдёте.
Ну, цыплят по осени считают.
Re: женский разум
Date: 2014-06-23 08:43 pm (UTC)Но изучать начным методом мир нелепо. Если вы вчера поставили в холодильник пиво, а утром его там не оказалось, вы будете проводить 25 раз экперимент?
Добытые знания другими людьми проверять не надо, это выпил сосед по общаге. Так же вы верите в учебник сопромата,когда поезд проезжает по мосту.
Re: женский разум
Date: 2014-06-23 09:35 pm (UTC)Учебник сопромата я скачать могу, и почитать. Ну и статей полно.
А про мозги давайте ссылку на ваши источники.
Re: женский разум
Date: 2014-06-24 05:29 am (UTC)Re: женский разум
Date: 2014-06-24 09:27 am (UTC)PubMed, Science, Nature, в принципе и российские рецензируемые журналы тоже подошли бы.
no subject
Date: 2014-06-23 02:27 pm (UTC)So it's not good; but in general, can the tree we build serve as the stack? That's what I was asking.
no subject
Date: 2014-06-23 05:28 pm (UTC)no subject
Date: 2014-06-26 06:18 am (UTC)