Tag Archives: python

Скільки слів треба щоб написати вікіпедію? І які зустрічаються частіше?

Виявляється відтоді як я рахував символи вікіпедії пройшло вже більше року. Рахував я їх за допомогою Go, хоча можна було сильно спростити собі життя і рахувати їх за допомогою Python і pywikipediabot. Сьогодні розкажу як, і як можна побачити з назви – рахуватимемо слова.

Я чомусь боявся що щоб порахувати слова пам’яті не вистачить, тому треба якусь базу даних. Або пробувати все в пам’яті, але аби комп’ютеру не стало погано якось обмежити доступну пам’ять. Але мої 4Gb використовувались лише щось трохи більше ніж на 40% для підрахунку всіх слів включно зі сторінками обговорень, категорій, шаблонів, сторінок опису файлів, і т.п. німецької вікіпедії.

В модулі pywikibot.pagegenerators є об’єкти XMLDumpOldPageGenerator і XMLDumpPageGenerator. Вони приймають назву архіву з XML дампом в конструкторі, а після створення по них можна ітеруватися отримуючи об’єкти сторінки. Не ведіться на слово “Old” в назві першого об’єкта, це означає не депрекацію, а те що текст сторінки буде братись з дампа, а в другому випадку з дампа буде братись лише заголовки, а за свіжим текстом зроблять запит, що сповільнить обробку разів в 500. Тобто замість кількох годин ви будете чекати рік. 🙂

Я спробував проаналізувати німецьку вікіпедію (код буде пізніше), на це пішло 694 хв (трохи менше ніж 12 годин) і вийшло що в ній на 6,425,028 сторінках використовується 2,381,457,397 слів (приблизно 371 на сторінку), з них різних слів 18,349,393. В кінцевому результаті CSV з частотним словничком виходить на 300MB.

Серед тих що зустрічаються лише раз є слова типу PikettdienstPikettdienst (помилка парсера який видаляв розмітку), слово – це юридичний термін швейцарської німецької і перекладається як “служба за викликом”. І є слова на зразок Werkshöfe – подвір’я фабрик.

Топ 50 слів виглядає так, і складає 28% всіх слів загалом:

der 58761447 sich 9169933
und 49084873 wurde 9114619
die 44536463 CET 8614461
in 35684744 an 8385637
von 24448221 er 7835324
ist 20614114 dass 7550955
den 19454023 du 7435099
nicht 17519638 bei 7420172
das 17302844 Diskussion 7237855
zu 16167971 aus 7065523
mit 15906145 Artikel 6967243
im 15167140 oder 6824420
des 14661593 werden 6508092
für 14016308 war 6449858
auf 13957013 nach 6426826
auch 12849476 wird 6117566
eine 11903977 aber 6052645
ein 11780352 am 6017703
Kategorie 11369651 sind 5953632
als 11167157 Der 5623930
dem 11124726 Das 5545595
CEST 11104741 einen 5465687
ich 10886406 noch 5409154
Die 10761776 wie 5293658
es 10204681 einer 5228368

До списку потрапили такі вікіпедійно специфічні слова як Kategorie (сторінки без категорій вважаються не комільфо), CEST і CET (центральноєвропейський літній час і центральноєвропейський час, в підписах в обговореннях).

Ну а що без сторінок обговорень? Проблемав тому, що при створенні об’єкту сторінки XMLDumpOldPageGenerator бере з дампа лише текст і заголовок, простір імен залишається не заповненим і за замовчуванням 0 (основний). Є ще поле isredirect так при спробі доступу до нього знову здійснюється запит. Тому, краще перейти на рівень нижче і використати XmlDump з pywikibot.xmlreader, він використовується так само, просто дає об’єкти не Page, а попростіші, які не вміють робити запити до вікіпедії і не мають методу save. Але нам його й не треба, правда?

Ось код який ігнорує перенаправлення і всі сторінки крім статтей:

"""Count word frequencies in wikipedia dump"""
import csv
from collections import Counter
from itertools import islice
import re
import sys

import mwparserfromhell
from pywikibot.xmlreader import XmlDump

def main():
    """Iterate over pages and count words"""
    if len(sys.argv) < 2:
        print('Please give file name of dump')
        return
    filename = sys.argv[1]

    pages = 0
    words = 0
    words_counts = Counter()
    print('Processing dump')

    for page in XmlDump(filename).parse():
        if (page.ns != '0') or page.isredirect:
            continue
        try:
            text = mwparserfromhell.parse(page.text).strip_code()
        except Exception as e:
            print(page.title, e)
            continue

        text = text.replace('\u0301', '') # remove accents
        # Ukrainian: 

        # page_words = re.findall(
        #     r'[абвгґдеєжзиіїйклмнопрстуфхцчшщьюя'
        #     r'АБВГҐДЕЄЖЗИІЇЙКЛМНОПРСТУФХЦЧШЩЬЮЯ’\'-]+',
        #     text
        # )
        
        # Any language:
        page_words = re.findall(r'\b[^\W\d]+\b', text)

        pages += 1
        words += len(page_words)
        words_counts.update(page_words)
        if pages % 123 == 0:
            print('\rPages: %d. Words: %d. Unique: %d. Processing: %s' % (
                pages, words, len(words_counts), (page.title + ' ' * 70)[:70],
            ), end='')

    print('Done. Writing csv')
    with open('common_words.csv', 'w', newline='') as csvfile:
        csvwriter = csv.writer(csvfile)
        for item in words_counts.most_common():
            csvwriter.writerow(item)

if __name__ == '__main__':
    main()

Він працює майже вдвічі швидше, 381 хвилину, бо обробляє лише 2,295,426 сторінок (обсяг німецької вікіпедії цього року). На цих сторінках є 1,074,446,116 слів (в середньому 468 на сторінку), з них різних – 12,002,417. (Виявляється є аж 6 мільйонів всяких слів які вживаються на всіляких службових сторінках німецької вікіпедії, і яких нема в статтях).

Якщо ж взяти українські статті, то на них треба ще менше часу – 131 хвилину (забув уточнити що в мене SSD), їх є 923238 (скоро мільйон!), слів 238263126 (в середньому 258 на сторінку, треба доповнювати 😉 ). З них різних – 4,571,418. Отак, в мене тепер є частотний словник української на 4.5 мільйони слів. І німецької на 12 мільйонів.

Хоча не спішіть з висновками що українська мова бідніша, бо мої методи потребують вдосконалення. По перше, так як Morgen (ранок) і morgen (завтра) – різні слова, то я не приводив букви в німецькій до одного регістру. (Правда й в українській забув це зробити).

По друге, в німецькому словнику 350590 разів зустрічається слово “www”, бо я вважав словом будь-яку послідовність літер латинки, а в українській відфільтрував кирилицю. Слово youtube зустрічається 8375 разів, а значить є ризик знайти якесь рідкісне слово на зразок “fCn8zs912OE”. 🙂

На WordPress глючить додавання картинок, тому нате вам відео:

А, і ось топ-10 української вікіпедії:

в,4551982
на,3730686
і,3475086
у,3353796
з,3053407
-,2695783
Категорія,2417267
та,2350573
до,1815429
року,1553492

Частота “року” наводить на думку що в українській вікіпедії якийсь перекос на історичні методи викладу. 🙂

Docker і обмеження ресурсів

Раніше я вже писав собі шпаргалку по докеру, яка нікому крім мене майже не потрібна, тут буде додаток до неї.

Контейнери докера – це аналог процесів в ОС – тобто щось що запущено виконується. Запускаються імеджі (аналог виконуваної програми). Можна взяти готовий імедж, можна зробити свій за допомогою докерфайла (аналог коду програми), який описує як білдиться (аналог компіляції) імедж.

Загалом команда запуску контейнера виглядає так:

docker run $image_name [$command]

Наприклад якщо цікаво виконати якийсь код на останньому Python, але лінь його ставити, докер скачає і виконає:

docker run python:latest python -c "import sys; print(sys.version)"
# Unable to find image 'python:latest' locally
# latest: Pulling from library/python
# 22dbe790f715: Pull complete 
# ...
# 61b3f1392c29: Pull complete 
# Digest: sha256:c32b1a9fb8a0dc212c33ef1d492231c513fa326b4dae6dae7534491c857af88a
# Status: Downloaded newer image for python:latest
# 3.7.2 (default, Mar  5 2019, 06:22:51) 
# [GCC 6.3.0 20170516]

Якщо не передавати ніяку команду, контейнер виконуватиме ту що для нього задана за замовчуванням. Наприклад

docker run --name test_python_run python:latest # задаємо контейнеру ім'я щоб не сплутати з іншими:
docker ps -a
CONTAINER ID        IMAGE               COMMAND                  CREATED             STATUS                      PORTS                    NAMES
d95e1e13e3f2        python:latest       "python3"                5 seconds ago       Exited (0) 4 seconds ago                             test_python_run

Бачимо що контейнер запускав команду “python3” але вийшов з неї (бо термінал не приєднався). Щоб увійти в інтерактивну сесію, треба запускати так (-i вроді означає інтерактивно, тобто очікувати на stdin, -t – приєднати до поточного терміналу):

docker run -it python:latest

Тільки через командний рядок багато Python коду не передаш. Тому є два варіанти передати файли в контейнер. Перший – прямо в image, за допомогою dockerfile.

Візьмемо для експерименту такий скрипт що поступово пробує використати все більше й більше пам’яті:

import random
import time

data = []
for i in range(10 ** 6):
    data.append(random.random())
    if i % 1000 == 0:
        print(len(data))
        time.sleep(0.25)

Managing memory in Python is easy—if you just don’t care. Документація Theano.

Щоб створити з ним імедж достатньо такого докерфайлу:

FROM python:3.7
COPY script.py ./script.py
CMD python script.py

Тепер, щоб створити з нього імедж який називається наприклад memeater (зжирач пам’яті), треба виконати:

docker build -t memeater -f Dockerfile .

А щоб потім запустити цей контейнер:

docker run -t memeater

-t щоб бачити що він пише в stdout.

Далі ми можемо за допомогою команди docker stat спостерігати за тим скільки ресурсів цей контейнер їсть:

CONTAINER ID        NAME                CPU %               MEM USAGE / LIMIT   MEM %               NET I/O             BLOCK I/O           PIDS
8a58c19cc93c        exp                 0.28%               6.02MiB / 10MiB     60.20%              3.17kB / 0B         565kB / 1.01MB      2

Аби він не з’їв всю доступну пам’ять, можна йому обмежити ресурси:

docker run -t --name experiment --memory="10M" --cpus=0.1 memeater

Якщо вискакує повідомлення “WARNING: Your kernel does not support swap limit capabilities or the cgroup is not mounted. Memory limited without swap.”, значить у вас трохи не такий Linux, і обмеження стосуватиметься лише RAM, а не області підкачки. Задати параметр --memory-swap теж не допоможе.

Допоможе – взагалі відключити зберігання сторінок на диск.

docker run -t --name experiment --memory="20M" --memory-swappiness=0 --cpus=0.1 memeater

Якщо отримуєте помилку “docker: Error response from daemon: OCI runtime create failed: container_linux.go:344: starting container process caused “process_linux.go:424: container init caused \”\””: unknown.”, то це тому що обмеження по пам’яті за сильне. В мене при 10M вискакує, при 20 – ні.

Що відбувається коли пам’ять закінчується? Лог закінчується так:

492001
Killed

З цього експерименту можна зробити висновок що Python, запущений в системі з доступною пам’яттю 20 мегабайт може втримати в пам’яті трохи менше ніж пів мільйона чисел з плаваючою крапкою.

Геренуємо пару ключів для цифрового підпису за допомогою RSA в Python

Для тих кому викликати openssl надоїло. Це дивно, але цього нема в стандартній бібліотеці python, тому:

sudo pip install pycrypto

Тоді:

from Crypto.PublicKey import RSA
from Crypto import Random

private_key = RSA.generate(1024, Random.new().read)
public_key = private_key.publickey()

print(private_key.exportKey().decode('ascii'))
print(public_key.exportKey().decode('ascii'))

Що дасть нам:

-----BEGIN RSA PRIVATE KEY-----
MIICXQIBAAKBgQCFO0e8pxFV5Niq9Kjkn7HpX5xCbsh2oP56t2goNw/qZnddzW1x
... blablabla ...
dB6mvhutUqKRZDaA1o4y1kytKTG42RfEtdm8t1Z/77dS
-----END RSA PRIVATE KEY-----
-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCFO0e8pxFV5Niq9Kjkn7HpX5xC
bsh2oP56t2goNw/qZnddzW1xW3rWxYI2/Jxp/hv7EGapg12EcViF/C8Uv2WbCDEM
LIRaMqtHKFNaniscMgZKgaohkjXcLk5dIrVXuuxY7sk07BZqj+Jsv6xgR6GZ0CmG
Q3ZOmGAKksC/YA3gYwIDAQAB
-----END PUBLIC KEY-----

В іншій публікації було показано як це робити допомогою openssl, і як цими ключами підписати токен.

Як написати бота до Telegram?

Легко. 🙂 Давайте напишемо бота який перекладатиме нам всяке з німецької:

Приклад діалогу

Для цього нам треба поговорити з botFather-ом:

А зараз трохи не по темі цієї статті. Ось код який перетворює вікідані на словник, шукаючи всі сутності які мають мітки однією мовою, а потім показучи їх мітки іншою мовою, використовуючи хитрий запит SPARQL:

import json
import requests

def translate(from_lang, to_lang, word):
    '''
        Переклдає мітки елементів вікіданих з мови на мову. Повертає список варіантів перекладу
    '''
    res = sparql('''
        SELECT  ?ukLabel WHERE {
          ?item ?label "%s"@%s.
          ?item rdfs:label ?ukLabel filter(lang(?ukLabel) = "%s")
        } LIMIT 10
    ''' % (word, from_lang, to_lang))
    return list(map(
        lambda e: e['ukLabel']['value'],
        res['results']['bindings']
    ))

def sparql(query):
    ''' Отримує JSON дані запиту SPARQL до вікіданих '''
    res = requests.get(
        'https://query.wikidata.org/sparql',
        params={
            'query': query,
            'format': 'json'
        }
    )
    return json.loads(res.text)

А тепер повертаємось до теми телеграмного бота. Аби його написати треба поставити бібліотеку:

pip install pyTelegramBotAPI

Ось її Github: https://github.com/eternnoir/pyTelegramBotAPI

А далі – елементарно як писати консольну програму:

import telebot

TOKEN = '' # тут вставити те що BotFather сказав

bot = telebot.TeleBot(TOKEN)

@bot.message_handler(content_types=["text"]) # Якщо прийдуть нові повідомлення
def respond_to_message(message):
    translations = translate('de', 'uk', message.text) # Отримати переклади тексту повідомленя
    resp = '\n'.join(translations) if translations else 'На жаль, перекладу слова %s не знайдено' % message.text
    bot.send_message( # відправити назад
        message.chat.id, # в той самий чат з якого прийшло (можна напевне й в інший)
        resp
    )

if __name__ == '__main__':
     bot.polling(none_stop=True) # Запустити бота аби той сидів на лінії і слухав повідомлення.

Поки що все, бо й висипатись іноді треба. Пізніше нагадайте мені не забути написати більше про SPARQL, як поставити собі локальну mediawiki і розширення до неї, як логінити сторонні застосунки через OAuth, і як переписати інтерфейс вікіпедії на Vue.js. 🙂


Filed under: Кодерство, Павутина Tagged: вікіпедія, Python

Побудова “скриньок з вусами” львівських квартир що здаються на сьогодні

Я ще минулого року помітив що в питаннях про Python на StackOverflow обговорюють якісь панди. Це, як виявилось обгортка навколо matplotlib, numpy і подібних гарних речей. А ще, лазячи по своїх документах в Google знайшов скачану вже позаминулого року стіну групи пошуку нерухомості вконтакті. І так співпало що я і мій колега-аналітик зараз шукаємо квартиру у Львові. Я йому показав цей файл, і він загорівся бажанням проаналізувати ще якийсь сайт оголошень.

При всій повазі до lun.ua, але тут я прорекламую dom.ria.com. Передовсім, там є українська версія. А ще, можливість скачати результати пошуку як електронну таблицю, хоч і в xls форматі, і лише одну сторінку.

В python читати xls вміє бібліотека xlrd, тому треба доставити ще й її. Pandas взагалі має багато необов’язкових залежностей:

sudo pip3.5 install jupyter pandas xlrd matplotlib
jupyter notebook # дуже модний графічний інтерпретатор

Якщо все поставити як вище і запустити “jupyter”, то можна робити обчислення в отакому документі: https://github.com/bunyk/mypandas/blob/master/dom.ria/dom.ria.ipynb

І можна побудувати графік скринька з вусами:


От, недаремно я деякі лекції з АнДану все таки не проспав! Хоча, який висновок робити з цього графіка – не знаю. Знаю лише що половина квартир потрапляють всередину прямокутника.

А ось гістограми по цінах для однокімнатних і двокімнатних:

Однокімнатні

Однокімнатні

Двокімнатні

Двокімнатні

Який з цих гістограм робити висновок окрім того що квартир дешевших за 2000 грн (окрім викидів) не буває (а я зараз живу за 700 грн/міс, хоча це пів квартири) – теж не знаю. Може ви самі якийсь зробите. І так, до речі, я шукаю одно чи двокімнатну квартиру десь в другому або третьому квартилі цін в районі вулиці Липинського.


Filed under: Інструменти, Кодерство, Павутина Tagged: графіка, математика, Python

Теорія взаємодії процесів (насправді про IT-Arena)

Я не дуже хотів йти на Львів ІТ арену, бо то настільки понтово що задорого. Крім того на вузькоспеціалізованих конференціях на зразок PyCon я мало що розумію, навіть якщо сам доповідаю. 🙂 Хоча, знаєте, ото щойно передивився одну доповідь – і ніби все зрозумів (а що ще краще, виявляється що викладені там ідеї я зараз використовую в Angular, хоч і забув про них). Крім того, нащо йти на платну конференцію, якщо ти навіть не встигаєш читати всі блоги і дивитись всі безкоштовні відео доповідей з інших конференцій в інтернеті?

Але я пішов, і не пожалів. Познайомився з Естер Дайсон. Вона великий фанат здорового способу життя, і інвестор в наш проект.

Пішов на доповідь про мікросервіси оцього чоловіка. Там дізнався що всі системи які містять багато взаємодіючих компонентів можна описувати наприклад пі-численням. Але так як книжки з пі-числення страшенно дорогі, ось вам безкоштовна про математичну теорію названу “Взаємодія послідовних процесів”, і написана не аби-ким, а Сером Чарлзом Ентоні Річардом Гоаром. Тепер залишилось знайти час прочитати.

А ще поміж іншим дізнався про те що програмне забезпечення це лайно (точніше завжди знав), але існує стрібна куля. Називається LangSec, коли ми вхідні параметри описуємо якоюсь формальною мовою. Чим це відрізняється від Логіки Хоара і наприклад статичної типізації з алгебраїчними типами даних – ще треба подумати.

А ще зустрів хлопців з Quintagroup, вони зразу такі “О, це ти той пітонщик з SoftServe що пише на Zope”. Я такий – той, але вже не пітонщик і не з SoftServe. 🙂 Зараз вони багато працюють над проектом Prozorro, і шукають нових людей. Тому якщо знаєте Pyramid (чи який там фреймворк у https://github.com/openprocurement), шукаєте роботу – напишіть їм.


Filed under: Кодерство, Нещоденник Tagged: математика, робота, Python

Проста схема перетворення інтерактивної процедурної програми з goto в функціональну рекурсивну

Власне вся передмова помістилась в заголовок. Хоча може для цього “паттерну” є коротша назва.

Існує клас інтерактивних програм які очікують вводу користувача, потім залежно від того вводу щось роблять, потім знову очікують вводу і так далі. Наприклад якась така програма “вгадай число”:

import random

def game():
    print('Як тебе звуть?')
    user = input()

    print('Привіт,', user)
    print('Давай пограємо гру відгадай число?')

    while True:
        number = random.randint(1, 10)
        print('Я загадав число від 1 до 10.')
        print('Спробуєш вгадати?')

        while True:
            print('Вводь свій варіант:')
            guess = input()
            if guess == number:
                print('Ого, так швидко вгадав. Грати ще раз?')
                while True:
                    answer = input()
                    if answer in ('так', 'ні'):
                        break
                    print('Ну то так чи ні?');

                if (answer == 'ні'):
                    print('Ну тоді бувай!')
                    return
                if (answer == 'так'):
                    break
            else:
                print('Ні, моє число ' +
                    ('більше' if (scope.guess < scope.number) else 'менше')
                    + ', пробуй ще'
                )
game()

JavaScript має з такими програмами проблему, бо він ніколи не зупиняється очікуючи на ввід користувача (якщо не рахувати функції alert() та компанії, він викликає функції які обробляють події, як от подію вводу. Щоб написати подібну програму для браузера, ми повинні реалізувати в ньому щось на зразок “консолі”:

<!DOCTYPE html>
<html>
<head>
    <meta charset="utf-8" />
</head>
<body>
    <pre id="console"></pre>
    <input type="text" id="input" />

<script>
(function() {
    var input = document.getElementById('input');
    var output = document.getElementById('console');

    var write = function(text) {
        // Write text to console
        output.innerHTML += text;
    };
    var writeln = function(text) {
        // Write line to console
        write(text + 'n');
    };
    
    // Register default callback of echoing input
    var input_callbacks = [function(input) {
        writeln('> ' + input);
    }];

    var on_input = function(callback) {
        // Register input callback

        input_callbacks[1] = callback;
    }

    input.onkeyup = function(e) {
        // Call all callbacks on input
        if (e.keyCode == 13) { // Enter pressed
            for(var i=0; i < input_callbacks.length; i++) {
                input_callbacks[i](input.value);
            }
            input.value = '';
        }
    };

    // Module exports:
    window.CLI = {
        write: write,
        writeln: writeln,
        on_input: on_input
    };
}());
</script>

<script>
// Ну а тут буде наша програма для "консолі". 
</script>
</body>
</html>

Ми маємо модуль CLI, який містить три функції. write та writeln дописують до елемента “консоль” переданий їм текст, а функція передана в on_input, буде викликатись отримуючи вміст елемента input коли в ньому натиснуть Enter. Проблема якраз в тому що буде викликатись окрема функція, якій передадуть ввід, і нема функції яка б той ввід просто повернула. Як написати для такої консолі інтерактивну гру “вгадай число”?

Тут на допомогу може прийти цікаве визначення алгоритму, яке я знайшов в книжці “Мистецтво програмування” Дональда Кнута (ні, я її не осилив, не зміг запам’ятати набір інструкцій MIX, хоча може варто пошукати якийсь емулятор цієї машини, щоб та книжка веселіше проходилась).

Так от, Кнут пише що будь-яку програму можна задати фунцією P(step, scope), яка приймає набір аргументів scope (що може бути одним аргументом – словником). Таким чином ми уникаємо зміни стану і оператора присвоєння, викликаючи функцію рекурсивно з новини аргументами.

Тому наприклад таку програму написану на бейсікоподібному псевдокоді:

    i = 0
1:  writeln i
    i = i + 1
    goto 1

Можна переписати на JavaScript рекурсивно так:

    function exec(step, scope) {
        CLI.writeln(scope.i);
        exec(step, {i: scope.i+1});
    }

    exec(1, {x: 0});

Варто також зауважити що JavaScript не має оптимізації хвостової рекурсії, тому така програма в Firefox зупиняється вивівши число 11085, і пожалівшись в консоль повідомленням “too much recursion”.

Тобто правило таке – як тільки ми хочемо змінити стан – ми викликаємо нашу функцію яка задає програму передавши їй цей новий стан. Ми також можемо робити умовні і безумовні переходи, викликаючи нашу функцію з різними значеннями параметра step. Подивимось як ми зможемо переписати програму гри “вгадай число”, яку описали вище на JavaScript. Але для цього спершу перепишемо її на наш діалект BASIC:

1:  writeln 'Як тебе звуть?'
    input user
2:  writeln 'Привіт,' + user
    writeln 'Давай пограємо гру "Відгадай число"?'
3:  writeln 'Я загадав число від 1 до 10.'
    number = randint(1, 10)
    writeln 'Спробуєш вгадати?'
4:  writeln 'Вводь свій варіант:'
    input guess
5:  if guess == number then 9
6:  if guess < number then 8
7:  writeln 'Ні, моє число менше, пробуй ще' 
    goto 4
8:  writeln 'Ні, моє число більше, пробуй ще'
    goto 4
9:  writeln 'Ого, так швидко вгадав. Грати ще раз?')
    input answer
10: if anwser == 'так' then 3
11: if answer == 'ні' then 13
12: writeln 'Ну то так чи ні?'
    input answer
    goto 10
13: writeln 'Ну тоді бувай!'

Тепер переписуємо цю програму на JavaScript за такими правилами:

  1. Кожен набір операторів що починається міткою ми записуємо в блок:
    if (step == 1 /*мітка*/) {
        // Код сюди
        return;
    };
    
  2. Кожне присвоєння відбувається в scope:
    if (...) {
        scope.number = Math.floor(Math.random() * 10) + 1;
        ...
        return;
    };
    
  3. Кожен блок що закінчується goto закінчується викликом exec:
    if (...) {
        // Код сюди
        exec(4 /* куди послало goto */, scope);
        return;
    };
    
  4. Кожен блок що закінчується if then:
    if (...) {
        // Код сюди
        if (...) {
            exec(3 /* куди послав then */, scope);
        } else {
            exec(11 /* перехід до наступного блоку */, scope);
        }
        return;
    };
    
  5. Кожен блок що закінчується input закінчується викликом exec для наступного кроку в callback:
    if (...) {
        // код сюди
        CLI.on_input(function(input) {
            scope.guess = input;
            exec(5, scope);
        });
        return;
    }
    
  6. Програма починається без змінних і з першого кроку:
    exec(1, {});
    

Таким чином з “бейсіка” на JavaScript програму можна переписати так:

function exec(step, scope) {
    // 1:  writeln 'Як тебе звуть?'
    //     input user
    if (step == 1) {
        CLI.writeln('Як тебе звуть?');
        CLI.on_input(function(input) {
            scope.user = input;
            exec(2, scope);
        });
        return;
    };
    // 2:  writeln 'Привіт,' + user
    //     writeln 'Давай пограємо гру "Відгадай число"?'
    if (step == 2) {
        CLI.writeln('Привіт, ' + scope.user);
        CLI.writeln('Давай пограємо гру "Відгадай число"?');
        exec(3, scope);
        return;
    };
    // 3:  writeln 'Я загадав число від 1 до 10.'
    //     number = randint(1, 10)
    //     writeln 'Спробуєш вгадати?'
    if (step == 3) {
        CLI.writeln('Я загадав число від 1 до 10.');
        scope.number = Math.floor(Math.random() * 10) + 1;
        CLI.writeln('Спробуєш вгадати?');
        exec(4, scope);
        return;
    };
    // 4:  writeln 'Вводь свій варіант:'
    //     input guess
    if (step == 4) {
        CLI.writeln('Вводь свій варіант:');
        CLI.on_input(function(input) {
            scope.guess = input;
            exec(5, scope);
        });
        return;
    };
    // 5:  if guess == number then 9
    if (step == 5) {
        if (scope.guess == scope.number) {
            exec(9, scope)
        } else {
            exec(6, scope)
        };
        return;
    };

    // 6:  if guess < number then 8
    if (step == 6) {
        if (scope.guess < scope.number) {
            exec(8, scope)
        } else {
            exec(7, scope)
        };

        return;
    };

    // 7:  writeln 'Ні, моє число менше, пробуй ще' 
    //     goto 4
    if (step == 7) {
        CLI.writeln('Ні, моє число менше, пробуй ще');
        exec(4, scope)
        return;
    };

    // 8:  writeln 'Ні, моє число більше, пробуй ще'
    //     goto 4
    if (step == 8) {
        CLI.writeln('Ні, моє число більше, пробуй ще');
        exec(4, scope)
        return;
    };

    // 9:  writeln 'Ого, так швидко вгадав. Грати ще раз?')
    //     input answer
    if (step == 9) {
        CLI.writeln('Ого, так швидко вгадав. Грати ще раз?');
        CLI.on_input(function(input) {
            scope.answer = input;
            exec(10, scope);
        });
        return;
    };

    // 10: if anwser == 'так' then 3
    if (step == 10) {
        if (scope.answer == 'так') {
            exec(3, scope)
        } else {
            exec(11, scope)
        };

        return;
    };

    // 11: if answer == 'ні' then 13
    if (step == 11) {
        if (scope.answer == 'ні') {
            exec(13, scope)
        } else {
            exec(12, scope)
        };
        return;
    };

    // 12: writeln 'Ну то так чи ні?'
    //     input answer
    //     goto 10
    if (step == 12) {
        CLI.writeln('Ну то так чи ні?');
        CLI.on_input(function(input) {
            scope.answer = input;
            exec(10, scope);
        });
        return;
    };

    // 13: writeln 'Ну тоді бувай!'
    if (step == 13) {
        CLI.writeln('Ну тоді бувай!');
        CLI.on_input(function() {}); 
        return;
    };
}

exec(1, {});

Можна звісно коротше, якщо робити умовний оператор без переходів в інший блок:

function exec(step, scope) { 
    console.log(step, scope);
    if (step == 1) {
        CLI.writeln('Як тебе звуть?');
        CLI.on_input(function(input) {
            scope.user = input;
            exec(2, scope);
        });
        return;
    }
    if (step == 2) {
        CLI.writeln('Привіт,' + scope.user);
        CLI.writeln('Давай пограємо гру відгадай число?');
        exec(3, scope);
        return;
    }
    if (step == 3) {
        CLI.writeln('Я загадав число від 1 до 10.');
        scope.number = Math.floor(Math.random() * 10) + 1;
        CLI.writeln('Спробуєш вгадати?');
        exec(4, scope);
        return;
    }
    if (step == 4) {
        CLI.writeln('Вводь свій варіант:');
        CLI.on_input(function(input) {
            scope.guess = input;
            exec(5, scope);
        });
        return;
    }
    if (step == 5) {
        if (scope.guess == scope.number) {
            CLI.writeln('Ого, так швидко вгадав. Грати ще раз?')
            CLI.on_input(function(input) {
                scope.answer = input;
                exec(6, scope);
            });
            return;
        }
        CLI.writeln('Ні, моє число ' +
            (scope.guess < scope.number ? 'більше': 'менше')
            + ', пробуй ще');
        exec(4, scope);
        return;
    }
    if (step == 6) {
        if (scope.answer == 'так') {
            exec(3, scope);
            return;
        }
        if (scope.answer == 'ні') {
            CLI.writeln('Ну тоді бувай!');
            CLI.on_input(function(){});
            return;
        }
        CLI.writeln('Ну то так чи ні?');
        CLI.on_input(function(input) {
            scope.answer = input;
            exec(6, scope);
        });
        return;
    }

};

exec(1, {});

Які з цього висновки? Ми можемо уникнути зайвих вкладень якщо нам треба зробити ланцюзок колбеків – запит, обробка відповіді, новий запит що залежить від результатів, обробка відповіді і т.д. Головне, аби це не був ланцюжок з тисяч колбеків, бо нарвемось на переповнення стеку. Тоді доведеться писати власну оптимізацію хвостової рекурсії.


Filed under: Кодерство Tagged: книжки, JavaScript, розробка, Python

Встановлення Python 3.5 з джерельного коду, встановлення Django

Ок, продовжу спроби підготуватись до DjangoGirls так, щоб там ми вчили найпередовіші технології. :)

Такі експерименти краще робити у захищеному середовищі, тому бажано щоб у вас були VirtualBox та Vagrant:

sudo apt-get install virtualbox vagrant

Поки вони ставляться, раджу коротко ознайомитись як користуватись тим Vagrant-ом.

В директорії з кодом створюємо такий файл:

# -*- mode: ruby -*-
# vi: set ft=ruby :

VAGRANTFILE_API_VERSION = "2"

Vagrant.configure(VAGRANTFILE_API_VERSION) do |config|
  config.vm.box = "ubuntu/trusty64"
  config.vm.network "forwarded_port", guest: 8000, host: 8000
end

Це поки що він такий. Пізніше поміняю, і вся інсталяція має більш автоматизуватись. Тепер команда vagrant up дозволяє підняти чисте середовище. vagrant ssh – зайти в його термінал.

Ми хочемо Python 3.5, а його інакше як з сорсів не отримаєш, тому качаємо з сайту: https://www.python.org/downloads/

sudo apt-get update
sudo apt-get install build-essential libsqlite3-dev sqlite3 bzip2 libbz2-dev
sudo apt-get install libreadline-dev libncurses5-dev tk-dev libssl-dev
wget -c https://www.python.org/ftp/python/3.5.0/Python-3.5.0.tar.xz
tar xJf Python-3.5.0.tar.xz
cd Python-3.5.0
./configure
make
sudo make install

Тепер нарешті можна створювати віртуальне середовище (всередині віртуальної машини, ага), і ставити Django:

mkdir djangogirls
cd djangogirls
python3.5 -m venv myenv
source myenv/bin/activate
pip install django

Та-дааммм!!!

Successfully installed django-1.9

Не знав що вже є Django 1.9. Хоча, звісно що не знав, його вчора випустили. Кажуть там змінили дизайн адмінки. Давайте швиденько подивимось:

django-admin startproject mysite .
python manage.py migrate
python manage.py createsuperuser
python manage.py runserver
Адмінка як адмінка.

Адмінка як адмінка.


Filed under: Інструменти, Кодерство Tagged: linux, Python

EBNF Parser Kata

Ката – то вправа в східних бойових мистецтвах, набір рухів які треба повторювати поки не засвоїш досконально. Термін застосовується також і для неробочого, неспортивного, самостійного учбового програмування поза якимось проектом.

На моєму домашньому модемі відвалився DSL, то я вчора ввечері не мав чим зайнятись. (Хоча звісно є купа важливіших речей) Зате біля мене була роздруківка книжечки Ніклауса Вірта “Compiler Construction“, то я взявся перекладати його парсер EBNF що ілюструє метод рекурсивного спуску з Oberon на Python. Вийшло ніби незле:

# ebnf.py
import re

class Symbol(object):
    instances = {}
    def __init__(self, name, pattern):
        self.pattern = pattern
        self.regexp = re.compile(pattern)
        self.instances[name] = self

    def match(self, text):
        text = text.lstrip()
        m = self.regexp.match(text)
        if m:
            return m.group(), text[len(m.group()):]

    @classmethod
    def get_next(cls, text):
        if not text.strip():
            return 'empty', '', ''
        for name, sym in cls.instances.items():
            m = sym.match(text)
            if m:
                return name, m[0], m[1]
        raise UnknownSymbolError('Unknown symbol: %r' % text[:50] + (
            '...' if len(text) > 50 else ''
        ))

Symbol('ident', 'w+')
Symbol('literal', '"[^"]*"')
Symbol('eql', '=')
Symbol('lparen', '(')
Symbol('rparen', ')')
Symbol('lbrak', '[')
Symbol('rbrak', ']')
Symbol('lbrace', '{')
Symbol('rbrace', '}')
Symbol('bar', '|')
Symbol('period', '.')

EBNF = '''
syntax = {production}.
production = identifier "=" expression ".".
expression = term {"|" term}.
term = factor {factor}.
factor = identifier | string | "(" expression ")" | "[" expression "]" | "{" expression "}".
'''

def parse_ebnf(text):
    sym, sym_text, remaining = '', '', text
    
    def next():
        nonlocal sym, sym_text, remaining
        sym, sym_text, remaining = Symbol.get_next(remaining)

    next()
    
    def syntax():
        res = ['syntax']
        while sym == 'ident':
            res.append(production())
        return res

    def production():
        name = sym_text
        next()
        if sym == 'eql':
            next()
        else:
            raise ExpectedEqualityError
        exp = expression()
        if sym == 'period':
            next()
        else:
            raise NoPeriodError
        return ['production', name, exp]

    def expression():
        res = ['expression', term()]
        while sym == 'bar':
            next()
            res.append(term())
        return res

    def term():
        res = ['term']
        while sym in ('ident', 'literal', 'lparen', 'lbrak', 'lbrace'):
            res.append(factor())
        if len(res) == 1:
            raise NoFactorError
        return res

    def factor():
        if sym == 'ident':
            res = [sym, sym_text]
            next()
            return res
        elif sym == 'literal':
            res = [sym, sym_text]
            next()
            return res
        elif sym == 'lparen':
            next()
            exp = expression()
            if sym == 'rparen':
                next()
            else:
                raise NoRParenError
            return ['(', exp]
        elif sym == 'lbrak':
            next()
            exp = expression()
            if sym == 'rbrak':
                next()
            else:
                raise NoRBrakError
            return ['[', exp]
        elif sym == 'lbrace':
            next()
            exp = expression()
            if sym == 'rbrace':
                next()
            else:
                raise NoRBraceError
            return ['{', exp]
        else:
            raise RuntimeError(
                "term should be called only when "
                "sym in ('ident', 'literal', 'lparen', 'lbrak', 'lbrace')"
            )

    return syntax()

class UnknownSymbolError(SyntaxError):
    pass

class NoPeriodError(SyntaxError):
    pass

class NoRParenError(SyntaxError):
    pass

class NoRBrakError(SyntaxError):
    pass

class NoRBraceError(SyntaxError):
    pass

class NoFactorError(SyntaxError):
    pass

class ExpectedEqualityError(SyntaxError):
    pass

Трохи TDD, трохи дописування тестів після:

# test.py
from unittest import TestCase, main, skip

from ebnf import Symbol
from ebnf import parse_ebnf, EBNF
from ebnf import print_tree
from ebnf import (
    NoPeriodError, NoRParenError, UnknownSymbolError,
    NoRBrakError, NoRBraceError, NoFactorError
)

class TestSymbol(TestCase):
    def test_paren(self):
        self.assertEqual(
            Symbol.get_next('(asdf)'),
            ('lparen', '(', 'asdf)')
        )
    def test_ident(self):
        self.assertEqual(
            Symbol.get_next('asdf'),
            ('ident', 'asdf', '')
        )
    def test_bar(self):
        self.assertEqual(
            Symbol.get_next('|asdf'),
            ('bar', '|', 'asdf')
        )

class TestEBNF(TestCase):
    def test_self(self):
        tree = parse_ebnf(EBNF)
        self.assertEqual(
            parse_ebnf(EBNF),
            ['syntax',
             ['production',
              'syntax',
              ['expression',
               ['term', ['{', ['expression', ['term', ['ident', 'production']]]]]]],
             ['production',
              'production',
              ['expression',
               ['term',
                ['ident', 'identifier'],
                ['literal', '"="'],
                ['ident', 'expression'],
                ['literal', '"."']]]],
             ['production',
              'expression',
              ['expression',
               ['term',
                ['ident', 'term'],
                ['{', ['expression', ['term', ['literal', '"|"'], ['ident', 'term']]]]]]],
             ['production',
              'term',
              ['expression',
               ['term',
                ['ident', 'factor'],
                ['{', ['expression', ['term', ['ident', 'factor']]]]]]],
             ['production',
              'factor',
              ['expression',
               ['term', ['ident', 'identifier']],
               ['term', ['ident', 'string']],
               ['term', ['literal', '"("'], ['ident', 'expression'], ['literal', '")"']],
               ['term', ['literal', '"["'], ['ident', 'expression'], ['literal', '"]"']],
               ['term', ['literal', '"{"'], ['ident', 'expression'], ['literal', '"}"']]]]]
        )

    def test_without_period(self):
        with self.assertRaises(NoPeriodError):
            parse_ebnf('symbol = "asdf"')

    def test_without_rparen(self):
        with self.assertRaises(NoRParenError):
            parse_ebnf('symbol = ("asdf"')

    def test_without_rbrak(self):
        with self.assertRaises(NoRBrakError):
            parse_ebnf('symbol = ["asdf"')

    def test_without_rbrace(self):
        with self.assertRaises(NoRBraceError):
            parse_ebnf('symbol = {literal')

    def test_unknown_symbol(self):
        with self.assertRaises(UnknownSymbolError):
            parse_ebnf('!symbol = "asdf"')

    def test_no_factor(self):
        with self.assertRaises(NoFactorError):
            parse_ebnf('sym = ||')

    def test_for_binary(self):
        self.assertEqual(
            parse_ebnf('''
                digit = "0"|"1".
                number = digit {digit}.
            '''),
            ['syntax',
             ['production',
              'digit',
              ['expression', ['term', ['literal', '"0"']], ['term', ['literal', '"1"']]]],
             ['production',
              'number',
              ['expression',
               ['term',
                ['ident', 'digit'],
                ['{', ['expression', ['term', ['ident', 'digit']]]]]]]]
        )


if __name__ == '__main__':
    main()

І я зрозумів дві речі: що найбільше на світі (якщо не враховувати сну) люблю писати код, і що таке множина first_1(k). Якщо коротко, то це множина символів з яких може починатись рядок що виводиться з нетерміналу k. Наприклад:

digit = "0" | "1"
number = digit {digit}

first(number) = {"0", "1"}

І ми знаємо що парсер може прочитати не будь-яку граматику, а лише ту, в якої для кожного виразу на зразок

definition = exp1 | exp2

Виконується умова:

first_1(exp1) \cap first_1(exp2) = \varnothing

Таким чином отака граматика багатозначна:

sum = number | sum ("+" | "-") sum

Бо вираз 1 – 10 + 11 можна розпарсити як (1 – 10) + 11 або як 1 – (10 + 11). А все тому, що first(number) = first(sum).

Її можна переписати так щоб в правилі для суми не було двох варіантів що починаються з однакових символів.

sum = number {("+" | "-") number}

Так вся сума розгортатиметься зразу і не буде проблем з тим яку операцію виконувати швидше.

Тепер би ще змусити його автоматично генерувати код парсера за EBNF і вийде власний YACC. :)


Filed under: Кодерство Tagged: Python

EBNF Parser Kata

Ката – то вправа в східних бойових мистецтвах, набір рухів які треба повторювати поки не засвоїш досконально. Термін застосовується також і для неробочого, неспортивного, самостійного учбового програмування поза якимось проектом.

На моєму домашньому модемі відвалився DSL, то я вчора ввечері не мав чим зайнятись. (Хоча звісно є купа важливіших речей) Зате біля мене була роздруківка книжечки Ніклауса Вірта “Compiler Construction“, то я взявся перекладати його парсер EBNF що ілюструє метод рекурсивного спуску з Oberon на Python. Вийшло ніби незле:

# ebnf.py
import re

class Symbol(object):
    instances = {}
    def __init__(self, name, pattern):
        self.pattern = pattern
        self.regexp = re.compile(pattern)
        self.instances[name] = self

    def match(self, text):
        text = text.lstrip()
        m = self.regexp.match(text)
        if m:
            return m.group(), text[len(m.group()):]

    @classmethod
    def get_next(cls, text):
        if not text.strip():
            return 'empty', '', ''
        for name, sym in cls.instances.items():
            m = sym.match(text)
            if m:
                return name, m[0], m[1]
        raise UnknownSymbolError('Unknown symbol: %r' % text[:50] + (
            '...' if len(text) > 50 else ''
        ))

Symbol('ident', 'w+')
Symbol('literal', '"[^"]*"')
Symbol('eql', '=')
Symbol('lparen', '(')
Symbol('rparen', ')')
Symbol('lbrak', '[')
Symbol('rbrak', ']')
Symbol('lbrace', '{')
Symbol('rbrace', '}')
Symbol('bar', '|')
Symbol('period', '.')

EBNF = '''
syntax = {production}.
production = identifier "=" expression ".".
expression = term {"|" term}.
term = factor {factor}.
factor = identifier | string | "(" expression ")" | "[" expression "]" | "{" expression "}".
'''

def parse_ebnf(text):
    sym, sym_text, remaining = '', '', text
    
    def next():
        nonlocal sym, sym_text, remaining
        sym, sym_text, remaining = Symbol.get_next(remaining)

    next()
    
    def syntax():
        res = ['syntax']
        while sym == 'ident':
            res.append(production())
        return res

    def production():
        name = sym_text
        next()
        if sym == 'eql':
            next()
        else:
            raise ExpectedEqualityError
        exp = expression()
        if sym == 'period':
            next()
        else:
            raise NoPeriodError
        return ['production', name, exp]

    def expression():
        res = ['expression', term()]
        while sym == 'bar':
            next()
            res.append(term())
        return res

    def term():
        res = ['term']
        while sym in ('ident', 'literal', 'lparen', 'lbrak', 'lbrace'):
            res.append(factor())
        if len(res) == 1:
            raise NoFactorError
        return res

    def factor():
        if sym == 'ident':
            res = [sym, sym_text]
            next()
            return res
        elif sym == 'literal':
            res = [sym, sym_text]
            next()
            return res
        elif sym == 'lparen':
            next()
            exp = expression()
            if sym == 'rparen':
                next()
            else:
                raise NoRParenError
            return ['(', exp]
        elif sym == 'lbrak':
            next()
            exp = expression()
            if sym == 'rbrak':
                next()
            else:
                raise NoRBrakError
            return ['[', exp]
        elif sym == 'lbrace':
            next()
            exp = expression()
            if sym == 'rbrace':
                next()
            else:
                raise NoRBraceError
            return ['{', exp]
        else:
            raise RuntimeError(
                "term should be called only when "
                "sym in ('ident', 'literal', 'lparen', 'lbrak', 'lbrace')"
            )

    return syntax()

class UnknownSymbolError(SyntaxError):
    pass

class NoPeriodError(SyntaxError):
    pass

class NoRParenError(SyntaxError):
    pass

class NoRBrakError(SyntaxError):
    pass

class NoRBraceError(SyntaxError):
    pass

class NoFactorError(SyntaxError):
    pass

class ExpectedEqualityError(SyntaxError):
    pass

Трохи TDD, трохи дописування тестів після:

# test.py
from unittest import TestCase, main, skip

from ebnf import Symbol
from ebnf import parse_ebnf, EBNF
from ebnf import print_tree
from ebnf import (
    NoPeriodError, NoRParenError, UnknownSymbolError,
    NoRBrakError, NoRBraceError, NoFactorError
)

class TestSymbol(TestCase):
    def test_paren(self):
        self.assertEqual(
            Symbol.get_next('(asdf)'),
            ('lparen', '(', 'asdf)')
        )
    def test_ident(self):
        self.assertEqual(
            Symbol.get_next('asdf'),
            ('ident', 'asdf', '')
        )
    def test_bar(self):
        self.assertEqual(
            Symbol.get_next('|asdf'),
            ('bar', '|', 'asdf')
        )

class TestEBNF(TestCase):
    def test_self(self):
        tree = parse_ebnf(EBNF)
        self.assertEqual(
            parse_ebnf(EBNF),
            ['syntax',
             ['production',
              'syntax',
              ['expression',
               ['term', ['{', ['expression', ['term', ['ident', 'production']]]]]]],
             ['production',
              'production',
              ['expression',
               ['term',
                ['ident', 'identifier'],
                ['literal', '"="'],
                ['ident', 'expression'],
                ['literal', '"."']]]],
             ['production',
              'expression',
              ['expression',
               ['term',
                ['ident', 'term'],
                ['{', ['expression', ['term', ['literal', '"|"'], ['ident', 'term']]]]]]],
             ['production',
              'term',
              ['expression',
               ['term',
                ['ident', 'factor'],
                ['{', ['expression', ['term', ['ident', 'factor']]]]]]],
             ['production',
              'factor',
              ['expression',
               ['term', ['ident', 'identifier']],
               ['term', ['ident', 'string']],
               ['term', ['literal', '"("'], ['ident', 'expression'], ['literal', '")"']],
               ['term', ['literal', '"["'], ['ident', 'expression'], ['literal', '"]"']],
               ['term', ['literal', '"{"'], ['ident', 'expression'], ['literal', '"}"']]]]]
        )

    def test_without_period(self):
        with self.assertRaises(NoPeriodError):
            parse_ebnf('symbol = "asdf"')

    def test_without_rparen(self):
        with self.assertRaises(NoRParenError):
            parse_ebnf('symbol = ("asdf"')

    def test_without_rbrak(self):
        with self.assertRaises(NoRBrakError):
            parse_ebnf('symbol = ["asdf"')

    def test_without_rbrace(self):
        with self.assertRaises(NoRBraceError):
            parse_ebnf('symbol = {literal')

    def test_unknown_symbol(self):
        with self.assertRaises(UnknownSymbolError):
            parse_ebnf('!symbol = "asdf"')

    def test_no_factor(self):
        with self.assertRaises(NoFactorError):
            parse_ebnf('sym = ||')

    def test_for_binary(self):
        self.assertEqual(
            parse_ebnf('''
                digit = "0"|"1".
                number = digit {digit}.
            '''),
            ['syntax',
             ['production',
              'digit',
              ['expression', ['term', ['literal', '"0"']], ['term', ['literal', '"1"']]]],
             ['production',
              'number',
              ['expression',
               ['term',
                ['ident', 'digit'],
                ['{', ['expression', ['term', ['ident', 'digit']]]]]]]]
        )


if __name__ == '__main__':
    main()

І я зрозумів дві речі: що найбільше на світі (якщо не враховувати сну) люблю писати код, і що таке множина first_1(k). Якщо коротко, то це множина символів з яких може починатись рядок що виводиться з нетерміналу k. Наприклад:

digit = "0" | "1"
number = digit {digit}

first(number) = {"0", "1"}

І ми знаємо що парсер може прочитати не будь-яку граматику, а лише ту, в якої для кожного виразу на зразок

definition = exp1 | exp2

Виконується умова:

first_1(exp1) \cap first_1(exp2) = \varnothing

Таким чином отака граматика багатозначна:

sum = number | sum ("+" | "-") sum

Бо вираз 1 – 10 + 11 можна розпарсити як (1 – 10) + 11 або як 1 – (10 + 11). А все тому, що first(number) = first(sum).

Її можна переписати так щоб в правилі для суми не було двох варіантів що починаються з однакових символів.

sum = number {("+" | "-") number}

Так вся сума розгортатиметься зразу і не буде проблем з тим яку операцію виконувати швидше.

Тепер би ще змусити його автоматично генерувати код парсера за EBNF і вийде власний YACC. :)


Filed under: Кодерство Tagged: Python