let rule1 = [ [ "Z"; "d" ]; [ "Z"; "X"; "Y"; "Z" ]; [ "Y" ]; [ "Y"; "c" ]; [ "X"; "Y" ]; [ "X"; "a" ] ] let rule2 = [ [ "S'"; "L"; "$" ]; [ "L"; "S"; ";"; "L" ]; [ "L"; "S" ]; [ "S"; "id"; "="; "E" ]; [ "S"; "print"; "("; "E"; ")" ]; [ "E"; "T"; "E'" ]; [ "E'"; "+"; "T"; "E'" ]; [ "E'"; "-"; "T"; "E'" ]; [ "E'" ]; [ "T"; "F"; "T'" ]; [ "T'"; "*"; "F"; "T'" ]; [ "T'"; "/"; "F"; "T'" ]; [ "T'" ]; [ "F"; "id" ]; [ "F"; "num" ]; [ "F"; "("; "E"; ")" ] ] let rule3 = [ [ "S'"; "L"; "$" ]; [ "L"; "S"; "L'" ]; [ "L'"; ";"; "L" ]; [ "L'" ]; [ "S"; "id"; "="; "E" ]; [ "S"; "print"; "("; "E"; ")" ]; [ "E"; "T"; "E'" ]; [ "E'"; "+"; "T"; "E'" ]; [ "E'"; "-"; "T"; "E'" ]; [ "E'" ]; [ "T"; "F"; "T'" ]; [ "T'"; "*"; "F"; "T'" ]; [ "T'"; "/"; "F"; "T'" ]; [ "T'" ]; [ "F"; "id" ]; [ "F"; "num" ]; [ "F"; "("; "E"; ")" ] ] let rule4 = [ [ "S"; "E"; "$" ]; [ "E"; "F"; "+"; "T"]; [ "E"; "T" ]; [ "T"; "F" ]; [ "F"; "-"; "T"]; [ "F"; "num" ] ] let rule5 = [ [ "S"; "id"; ":="; "E" ]; [ "S"; "if"; "E"; "then"; "S"; "X"]; [ "X" ]; [ "X"; "else"; "S" ]; [ "E"; "T"; "E'" ]; [ "E'"; "+"; "T"; "E'" ]; [ "E'" ]; [ "T"; "num" ] ] let rule6 = [ ["S"; "E"; "$"]; ["E"; "id"]; ["E"; "id"; "("; "E"; ")"]; ["E"; "E"; "+"; "id"] ] exception Error let firstFollow rules = let re l = List.fold_left (fun rlt x -> if List.mem x rlt then rlt else rlt@[x]) [] l in let extNonTerm l = re (List.map (fun x -> List.hd x) l) in let extSym l = re (List.flatten l) in let nonTerms = extNonTerm rules in let terms = List.filter (fun x -> not (List.mem x nonTerms)) (extSym rules) in let syms = nonTerms@terms in let sLen = List.length syms in let nLen = List.length nonTerms in let ruleLen = List.length rules in let aRules = Array.of_list (List.map (fun x -> Array.of_list x) rules) in let aSyms = Array.of_list syms in let s2i sym = let rec search cnt l = match l with [] -> raise Error | h::rest -> if h = sym then cnt else search (cnt+1) rest in search 0 syms in let nullable = Array.make sLen false in let first = Array.make sLen [] in let follow = Array.make sLen [] in let init () = for i = 0 to sLen -1 do if List.mem aSyms.(i) terms then first.(i) <- [aSyms.(i)] done in let subL a x y = Array.to_list (Array.sub a x (y-x+1)) in let rec repeat () = let oldNullable = Array.copy nullable and oldFirst = Array.copy first and oldFollow = Array.copy follow in ( for r = 0 to ruleLen - 1 do let rule = aRules.(r) in (if (Array.length rule) = 1 || List.for_all (fun x -> nullable.(s2i x)) (List.tl (Array.to_list rule)) then nullable.(s2i rule.(0)) <- true; let len = Array.length rule in if len > 1 then for i = 1 to len-1 do if i = 1 || List.for_all (fun x -> nullable.(s2i x)) (subL rule 1 (i-1)) then first.(s2i rule.(0)) <- re (first.(s2i rule.(0)) @ first.(s2i rule.(i))); if i = len -1 || List.for_all (fun x -> nullable.(s2i x)) (subL rule (i+1) (len-1)) then follow.(s2i rule.(i)) <- re (follow.(s2i rule.(i))@follow.(s2i rule.(0))); if i < len -1 then for j = i+1 to len -1 do if j = i+1 || List.for_all (fun x -> nullable.(s2i x)) (subL rule (i+1) (j-1)) then follow.(s2i rule.(i)) <- re (follow.(s2i rule.(i))@first.(s2i rule.(j))); done done) done; if not (oldNullable = nullable) || not (oldFirst = first) || not (oldFollow = follow) then repeat()) in (init(); repeat(); for i=0 to nLen-1 do Printf.printf "nullable(%s):\t" aSyms.(i); if nullable.(i) then print_string "true\n" else print_string "false\n"; done; print_string "\n"; for i=0 to nLen-1 do Printf.printf "FIRST(%s):\t" aSyms.(i); List.iter (fun x -> Printf.printf "%s " x) first.(i); print_string "\n" done; print_string "\n"; for i=0 to nLen-1 do Printf.printf "FOLLOW(%s):\t" aSyms.(i); List.iter (fun x -> Printf.printf "%s " x) follow.(i); print_string "\n" done)