среда, 19 мая 2010 г.

Грамматика и её граф.

Моя сестра занимается весьма интересными вещами -- стохастическими грамматиками. Я в этих вещах понимаю далеко не всё, но иногда, в качестве побочных результатов исследований появляются всякие разные штуковины, которые близки и понятны обычному программисту. Так, для исследований, в качестве лабораторной мышки, с моей подачи, был выбран язык Оберон-2, который обладает одновременно двумя важными качествами: во-первых он весьма прост (по сравнению с другими ЯП), во-вторых он реально используется, и, что самое главное, можно найти некоторое количество исходников реальных программ и библиотек писаных на нем. Найти и проанализировать. Т.е. это правильная лабораторная мышка, а не какой-то там сферконь в великом ничто.

Кроме анализа исходников, в процессе анализируется и сама грамматика -- в ней ищутся классы нетерминалов. Для этого строится граф связей оных нетерминалов. И вот тут мы получаем побочный результат который может быть интересен в т.ч. и простому парню от программерской сохи -- визуальное представление оного графа грамматики реального ЯП:

(из графа удалены все терминалы)


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

4 комментария:

Zert комментирует...

Можно рисовать графы всяких протоколов, очень наглядно будет и поможет их изучению.

wlad комментирует...

Давайте сразу для Си++ , СИ-шарпа и Пшола! ВОт уж где наглядность будет - дальше некуда! :)

valexey комментирует...

На самом деле тут нужно очень вдумчиво и осторожно подходить к сравнению сложности синтаксиса языков путем сравнения описания их грамматик. Например любое сравнение описания грамматики С/С++/Java с описанием грамматики Оберона/Оберона-2 и их производных, будет не слишком корректно. Просто потому что описания делаются на разных языках. Грамматика оберона описывается на языке EBNF, грамматика C/C++/Java описывается на языке эквивалентном BNF. В BNF нет например способа указать повторы лексем, поэтому приходится использовать рекурсию и вводить новые нетерминалы. Следовательно описание становится длиннее, связи между нетерминалами сложнее, а самих нетерминалов больше.

Более того, возьмём для примера Oberon и Oberon-2. Первый является подмножеством второго (в плане синтаксиса), соответственно синтаксис Oberon-2 более сложен и разнообразен нежели синтаксис Oberon'a. Однако описание грамматики у Oberon-2 компактней и проще нежели у Oberon'a. Вывод -- авторы языка произвели оптимизацию описания грамматики.

Т.о. описание стало проще, но сам язык (его синтаксис, не говоря о семантике) сложнее.

Анонимный комментирует...

описания грамматик - равносильны. Какая разница - в каком формализме описывается? по сути - описание автомата.