გრამატიკა როგორც გრაფის სტრუქტურა
კომპილატორი თარგმნის წყაროს კოდს ანალიზის ხის აგებით — კორენიანი ხე, სადაც თითოეული კვანძი წარმოადგენს გამოყენებულ გრამატიკულ წესს, & თითოეული ფოთოლი წარმოადგენს ტერმინალურ სიმბოლოს (ცვლადის სახელი, ლიტერალი, ოპერატორი).
ხის გეომეტრია
ხე n კვანძით & n−1 კიდეებით. სიღრმე d: ფესვიდან ნებისმიერ ფოთოლამდე მაქსიმალური მანძილი. დაბალანსებული ორობითი ხის სიღრმით d: до 2^d ფოთოლი & 2^(d+1)−1 სულ კვანძი.
ტიპური გამოხატულებების ანალიზის ხეები არ არის დაბალანსებული: ოპერატორის უფრიშობა ქმნის მარჯვნივ-დახრილ ან მარცხნივ-დახრილ ხეებს. A + B C იწვევს ხეს, სადაც უფრო ღრმაა, ვიდრე +, კოდირება, რომ * უფრო მჭიდროდ ახშენს.
BNF & ALGOL
Backus-Naur Form (BNF), ALGOL-ის დასაკონკრეტოებლად გამოგონილი, გაფორმალებს გრამატიკას როგორც წარმოების წესებს:
``
<expr> ::= <term> | <expr> + <term>
<term> ::= <factor> | <term> * <factor>
<factor> ::= id | (<expr>)
``
თითოეული წარმოების წესი განსაზღვრავს ხის ერთ დონეს. გრამატიკა არის მიმართული გრაფი არა-ტერმინალურ სიმბოლოებზე; წინადადების ანალიზი გაწერს მეტყველებას გრაფის მეშვეობით საწყისი სიმბოლოდან ფოთლებამდე.
ანალიზის ხის სიღრმე & გამოხატულების სირთულე
გამოხატულებისთვის (A + B) * (C + D), ანალიზის ხეს აქვს კონკრეტული სტრუქტურა სტანდარტული ოპერატორის უფრიშობის ქვეშ.
ანალიზის ხის სიღრმე გავლენას ახდენს კომპილატორის კეთილმოწყობაზე: უფრო ღრმა ხეები მოითხოვენ უფრო მეტ სტეკის ჩარჩოებს რეკურსიული დაღმართი ანალიზის დროს.
შენონის ენტროპია & სიჭარბე
ჰამინგმა აღნიშნა, რომ ლაპარაკი ენა ~60% სიჭარბე, წერილობითი ენა ~40%. ამას აქვს ზუსტი ინფორმაციო-თეორიული მნიშვნელობა.
შენონის ენტროპია
წყაროსთვის, რომელიც წარმოქმნის სიმბოლოებს A ანბანიდან ალბათობებით {p₁, p₂, ..., pₙ}:
H = −Σ pᵢ log₂(pᵢ) (ბიტი სიმბოლოზე)
მაქსიმალური ენტროპია: ერთიანი განაწილება (ყველა სიმბოლო თანაბრად სავარაუდო). H_max = log₂(n) n სიმბოლოსთვის.
სიჭარბე R: ბიტების ფრაქცია, რომელიც ინფორმაციას არ ატარებს (შეიძლება ამოღებული იყოს შინაარსის დაკარგვის გარეშე):
R = 1 − H / H_max
თუ R = 0.4 (40% სიჭარბე): 40% ბიტი უძღვნება კონტექსტიდან წინასწარ განსაზღვრულებელი. არხი, რომელიც ინგლისური ტექსტი ატარებს 8 ბიტი/სიმბოლოზე, იყენებს მხოლოდ მის ტევადობის 60% ინფორმაციისთვის; 40% არის სტრუქტურა, რომელიც მიმღები უკვე იცის.
Error detection იყენებს სიჭარბეს: თუ 40% ბიტი წინასწარი განსაზღვრულებელი, გადაცემის შეცდომა შეიძლება აწარმოოს თანმიმდევრობა, რომელიც ღელავს სიჭარბის სტრუქტურას — შემჩნეული შესაძლებელი კიდეც error-correcting codes-ის გარეშე.
APL-ის თითქმის-ნულოვანი სიჭარბე: ერთი სიმბოლოს შეცვლა უმეტეს შემთხვევაში კონტექსტიდან შემჩნეული არ არის. ინგლისურის 60% სიჭარბე: შეგიძლია ხშირად აღადგინო სიტყვა გარშემო კონტექსტიდან კიდეც თუ ასო დაკარგული ან არასწორი.
სიჭარბის გამოთვლა
ინგლისური ასოს სიხშირე (დაახლოებითი): 'e' გამოჩნდება ~12.7% დროის; 'z' გამოჩნდება ~0.07%. ინგლისურის რეალური ენტროპია დაახლოებით H ≈ 1.0 ბიტი/სიმბოლო (სიტყვა-დონის კონტექსტის გამოყენებით). 26-ასოს ანბანის მაქსიმალური ენტროპია: H_max = log₂(26) ≈ 4.70 ბიტი/სიმბოლო.
ზრდის მრუდები როგორც გეომეტრია
კომპილატორი ალგორითმი ამუშავებს პროგრამები ზომით n (ტოკენი, ხაზი, ან კვანძი). ალგორითმის არჩევა განსაზღვრავს, თუ როგორ სკალირდება კომპილაციის დრო პროგრამის ზომასთან.
საერთო სირთულის კლასები
| კლასი | მოდიფიკაციის დრო | მაგალითი | |---|---|---| | O(n) | ხაზოვანი | ლექსიკალური სკანირება | | O(n log n) | quasi-linear | ოპტიმალური დახარისხება | | O(n²) | კვადრატული | naive duplicate detection | | O(n³) | კუბური | matrix multiply, CYK parsing | | O(2ⁿ) | exponential | naive theorem proving |
გეომეტრიული სურათი: plot დრო vs n-ზე. O(n) არის ხაზი. O(n²) არის პარაბოლა. O(2ⁿ) არის exponential მრუდი, რომელიც ჰგავს ბრტყელი n=0-ს ახლოს და თითქმის ვერტიკალური n=50 ახლოს.
General context-free grammar parsing (CYK algorithm) მოდის O(n³)-ში. უმეტეს პრაქტიკული დაპროგრამების ენებისთვის, გრამატიკა დიზაინი LR(1)-parseable, O(n) parsing დამთხვევა. ALGOL-ის გრამატიკა იყო უფრო კომპლექსი FORTRAN-ის ტესტებზე, კომპილატორის ნელი სიჩქარის კონტრიბუტორი — პრაქტიკული friction, რომელიც მნიშვნელოვანი იყო 1958 წელს როდესაც compiling საათში რომ გაჩერდა.
Crossover Points
naive symbol-table lookup იყენებს O(n²) ჯამური ოპერაციებს n identifiers პროგრამისთვის (ხაზოვანი scan თითოეული n lookups-ისთვის). hash-table symbol table იყენებს O(n) expected ჯამური ოპერაციებს.
ვთქვათ: O(n²) ალგორითმი მოდის 10⁶ ოპერაციებ/sec-ში 1958 აპარატურაზე. O(n) ალგორითმი მოდის იგივე სიჩქარით მაგრამ მოითხოვს 100n setup ოპერაციებს (hash table construction).