Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Trình biên dịch] Độ sâu đệ quy khi phân tích biểu thức số học

    Cho văn phạm sinh biểu thức số học không đệ quy trái sau (đã loại bỏ đệ quy trái để dùng cho phân tích cú pháp đệ quy):

    E→T E′E′→+ T E′∣− T E′∣εT→F T′T′→∗ F T′∣/ F T′∣εF→( E )∣soˆˊ\begin{aligned} E &\to T\ E' \\ E' &\to {+}\ T\ E' \mid {-}\ T\ E' \mid \varepsilon \\ T &\to F\ T' \\ T' &\to {*}\ F\ T' \mid {/}\ F\ T' \mid \varepsilon \\ F &\to (\ E\ ) \mid \text{số} \end{aligned}EE′TT′F​→T E′→+ T E′∣− T E′∣ε→F T′→∗ F T′∣/ F T′∣ε→( E )∣soˆˊ​

    Mỗi ký hiệu chưa kết thúc E,E′,T,T′,FE, E', T, T', FE,E′,T,T′,F tương ứng đúng một hàm đệ quy cùng tên. Khi phân tích một biểu thức, các hàm gọi lẫn nhau đúng theo thứ tự vế phải của luật sinh, từ trái sang phải: mỗi lần một hàm bắt đầu thực thi (được gọi), độ sâu ngăn xếp gọi hàm tăng thêm 1 đơn vị; khi hàm đó kết thúc (return), độ sâu giảm đi 1 đơn vị. Lời gọi khởi đầu là E()E()E() ở độ sâu 1.

    Ví dụ với luật F→( E )F \to (\ E\ )F→( E ): khi FFF gặp dấu (, nó gọi EEE (lồng bên trong FFF), rồi mới xử lý tiếp dấu ).

    Cho một biểu thức hợp lệ theo văn phạm trên (không cần xử lý lỗi), hãy xác định độ sâu lớn nhất mà ngăn xếp gọi hàm đạt tới trong toàn bộ quá trình phân tích cú pháp đệ quy nói trên.

    Ví dụ: với biểu thức 1+2:

    • EEE gọi ở độ sâu 1
    • EEE gọi TTT (độ sâu 2), TTT gọi FFF (độ sâu 3) đọc 1, FFF trả về (độ sâu 2), TTT gọi T′T'T′ (độ sâu 3, gặp + không khớp * / nên dừng ngay), T′T'T′ trả về (độ sâu 2), TTT trả về (độ sâu 1)
    • EEE gọi E′E'E′ (độ sâu 2): gặp +, E′E'E′ gọi TTT (độ sâu 3) →\to→ TTT gọi FFF (độ sâu 4) đọc 2 →\to→ trả về, TTT gọi T′T'T′ (độ sâu 4, dừng ngay) →\to→ trả về, TTT trả về (độ sâu 2); E′E'E′ gọi E′E'E′ đệ quy (độ sâu 3, gặp hết chuỗi nên dừng) →\to→ trả về

    Độ sâu lớn nhất đạt được là 444 (tại lời gọi FFF đọc số 2).

    • Định dạng đầu vào:

      Một dòng duy nhất chứa biểu thức, gồm các chữ số 0-9 (số nguyên không âm, có thể nhiều chữ số), các toán tử + - * / và dấu ngoặc tròn ( ), không chứa dấu cách. Biểu thức được đảm bảo hợp lệ theo văn phạm đã cho. Độ dài biểu thức không quá 200 ký tự.

    • Định dạng đầu ra:

      Một số nguyên duy nhất — độ sâu lớn nhất của ngăn xếp gọi hàm đệ quy khi phân tích biểu thức, theo đúng quy tắc gọi hàm mô tả ở trên.

    Ví dụ:

    Đầu vào:

    1+2

    Đầu ra:

    4

    Đầu vào:

    5

    Đầu ra:

    3

    Đang tải editor...