Ngữ pháp như cấu trúc đồ thị
Một trình biên dịch dịch mã nguồn bằng cách xây dựng một cây phân tích cú pháp — một cây có gốc trong đó mỗi nút biểu thị một quy tắc ngữ pháp được áp dụng, & mỗi lá biểu thị một ký hiệu cuối (tên biến, hằng số, toán tử).
Hình học cây
Một cây với n nút & n−1 cạnh. Độ sâu d: khoảng cách tối đa từ gốc đến bất kỳ lá nào. Đối với cây nhị phân cân bằng có độ sâu d: tối đa 2^d lá & 2^(d+1)−1 nút tổng cộng.
Cây phân tích cú pháp cho các biểu thức điển hình không cân bằng: ưu tiên toán tử tạo ra cây lệch phải hoặc lệch trái. A + B C tạo ra một cây trong đó sâu hơn +, mã hóa rằng * ràng buộc chặt hơn.
BNF & ALGOL
Hình thức Backus-Naur (BNF), được phát minh để xác định ALGOL, chính thức hóa ngữ pháp dưới dạng các quy tắc sản xuất:
``
<expr> ::= <term> | <expr> + <term>
<term> ::= <factor> | <term> * <factor>
<factor> ::= id | (<expr>)
``
Mỗi quy tắc sản xuất xác định một cấp độ của cây. Ngữ pháp là một đồ thị có hướng trên các ký hiệu không phải kết thúc; phân tích một câu truy vết một đường dẫn thông qua đồ thị đó từ ký hiệu bắt đầu đến lá.
Độ sâu cây phân tích & Độ phức tạp biểu thức
Đối với biểu thức (A + B) * (C + D), cây phân tích cú pháp có một cấu trúc cụ thể theo ưu tiên toán tử tiêu chuẩn.
Độ sâu của cây phân tích cú pháp ảnh hưởng đến hiệu suất trình biên dịch: các cây sâu hơn yêu cầu nhiều khung ngăn xếp hơn trong quá trình phân tích lạc đà đệ quy.
Entropy Shannon & Dư thừa
Hamming lưu ý rằng ngôn ngữ nói có ~60% dư thừa, ngôn ngữ viết ~40%. Điều này có ý nghĩa lý thuyết thông tin chính xác.
Entropy Shannon
Đối với một nguồn tạo ra các ký hiệu từ bảng chữ cái A với xác suất {p₁, p₂, ..., pₙ}:
H = −Σ pᵢ log₂(pᵢ) (bit trên mỗi ký hiệu)
Entropy tối đa: phân bố đều (tất cả các ký hiệu đều có khả năng xảy ra). H_max = log₂(n) cho n ký hiệu.
Dư thừa R: phần của bit không mang thông tin (có thể được loại bỏ mà không mất nội dung):
R = 1 − H / H_max
Nếu R = 0,4 (40% dư thừa): 40% của bit có thể được dự đoán từ ngữ cảnh. Một kênh truyền văn bản tiếng Anh với 8 bit/ký tự chỉ sử dụng 60% công suất của nó cho thông tin; 40% là cấu trúc mà người nhận đã biết.
Phát hiện lỗi sử dụng dư thừa: nếu 40% của bit có thể dự đoán được, một lỗi truyền có thể tạo ra một chuỗi vi phạm cấu trúc dư thừa — có thể phát hiện ngay cả không có mã sửa lỗi.
Dư thừa gần như không có của APL: một thay đổi ký tự duy nhất hầu như không bao giờ có thể phát hiện được từ ngữ cảnh một mình. Dư thừa 60% của tiếng Anh: bạn thường có thể tái tạo một từ từ ngữ cảnh xung quanh ngay cả khi một chữ cái bị thiếu hoặc sai.
Tính toán dư thừa
Tần suất chữ cái tiếng Anh (gần đúng): 'e' xuất hiện ~12,7% thời gian; 'z' xuất hiện ~0,07%. Entropy thực tế của tiếng Anh là khoảng H ≈ 1,0 bit/ký tự (tính đến ngữ cảnh cấp độ từ). Entropy tối đa cho bảng chữ cái 26 chữ: H_max = log₂(26) ≈ 4,70 bit/ký tự.
Đường cong tăng trưởng như hình học
Các thuật toán trình biên dịch xử lý các chương trình có kích thước n (mã thông báo, dòng hoặc nút). Sự lựa chọn thuật toán xác định cách thời gian biên dịch tăng theo kích thước chương trình.
Các lớp độ phức tạp phổ biến
| Lớp | Thời gian chạy | Ví dụ | |---|---|---| | O(n) | tuyến tính | quét từ vựng | | O(n log n) | gần tuyến tính | sắp xếp tối ưu | | O(n²) | bậc hai | phát hiện sao chép ngây thơ | | O(n³) | bậc ba | nhân ma trận, phân tích CYK | | O(2ⁿ) | hàm mũ | chứng minh định lý ngây thơ |
Hình ảnh hình học: vẽ biểu đồ thời gian chạy so với n. O(n) là một đường thẳng. O(n²) là một parabol. O(2ⁿ) là một đường cong hàm mũ trông phẳng gần n=0 & gần như thẳng đứng gần n=50.
Phân tích ngữ pháp ngữ cảnh tự do chung (thuật toán CYK) chạy trong O(n³). Đối với hầu hết các ngôn ngữ lập trình thực tế, ngữ pháp được thiết kế để được phân tích LR(1), cho phép phân tích O(n). Ngữ pháp của ALGOL phức tạp hơn FORTRAN, góp phần vào các trình biên dịch chậm hơn — một ma sát thực tế quan trọng vào năm 1958 khi biên dịch mất hàng giờ.
Điểm giao nhau
Tra cứu bảng ký hiệu ngây thơ sử dụng O(n²) tổng cộng các hoạt động cho một chương trình của n định danh (quét tuyến tính cho mỗi n tra cứu). Bảng ký hiệu bảng băm sử dụng O(n) tổng cộng các hoạt động dự kiến.
Giả sử: thuật toán O(n²) chạy ở 10⁶ hoạt động/giây trên phần cứng 1958. Thuật toán O(n) chạy với tốc độ tương tự nhưng yêu cầu 100n hoạt động thiết lập (xây dựng bảng băm).