我正在嘗試為我的brainf*ck 解釋器撰寫優化功能。它基本上將相同的指令組合成一條指令。
我寫了這個函式，但它不能正常作業：
pub fn optimize_multiple(instructions: &Vec<Instruction>) -> Vec<OptimizedInstruction> {
let mut opt: Vec<OptimizedInstruction> = Vec::new();
let mut last_instruction = instructions.get(0).unwrap();
let mut last_count = 0;
for instruction in instructions.iter() {
if instruction == last_instruction {
last_count = 1;
}
else if let Instruction::Loop(i) = instruction {
opt.push(OptimizedInstruction::Loop(optimize_multiple(i)));
last_count = 1;
}
else {
opt.push(OptimizedInstruction::new(last_instruction.clone(), last_count));
last_instruction = instruction;
last_count = 1;
}
}
opt
}
這是 OptimizedInstruction 列舉和“新”方法：（指令::回圈手只是一個占位符，我沒有使用它）
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum OptimizedInstruction {
IncrementPointer(usize),
DecrementPointer(usize),
Increment(usize),
Decrement(usize),
Write,
Read,
Loop(Vec<OptimizedInstruction>),
}
impl OptimizedInstruction {
pub fn new(instruction: Instruction, count: usize) -> OptimizedInstruction {
match instruction {
Instruction::IncrementPointer => OptimizedInstruction::IncrementPointer(count),
Instruction::DecrementPointer => OptimizedInstruction::DecrementPointer(count),
Instruction::Increment => OptimizedInstruction::Increment(count),
Instruction::Decrement => OptimizedInstruction::Decrement(count),
Instruction::Write => OptimizedInstruction::Write,
Instruction::Read => OptimizedInstruction::Read,
Instruction::Loop(_i) => OptimizedInstruction::Loop(Vec::new()),
}
}
}
我用這個輸入運行它：
-[ - ]
但它給了我這個輸出：
[Increment(2), Loop([Increment(1), Decrement(1)])]
插入這個：
[Increment(2), Decrement(1), Loop([Increment(1), Decrement(1), Increment(2)])]
我一直在嘗試解決它 2 天，但我仍然不知道它為什么不起作用。
~ 德林
uj5u.com熱心網友回復：
首先，為了在你的游行中下雨，我只想指出 Wilfred 已經用 Rust 制作了一個 Brainf*ck 編譯器，它可以通過 LLVM ( bfc) 編譯為本機二進制檔案。如果您遇到困難，您可能需要檢查他的實作，看看他是如何做到的。如果您忽略 LLVM 部分，則通讀起來并不難，而且他有一個很好的方法。
當分解為其核心組件時，這個問題圍繞著將兩個元素合并在一起。我遇到的解決這個問題的最優雅的方法是使用帶有合并功能的迭代器。我寫了一個我想象的例子，如下所示。我縮短了一些變數名稱，因為它們有點長，但總體思路是一樣的。合并函式有一個非常簡單的作業。當給定兩個元素時，嘗試將它們合并為一個新元素。然后迭代器處理將它們放入該函式并在它們不再可以合并時回傳專案。如果你愿意的話，一種可選的折疊。
pub struct MergeIter<I: Iterator, F> {
iter: I,
func: Box<F>,
held: Option<<I as Iterator>::Item>,
}
impl<I, F> Iterator for MergeIter<I, F>
where
I: Iterator,
F: FnMut(&<I as Iterator>::Item, &<I as Iterator>::Item) -> Option<<I as Iterator>::Item>,
{
type Item = <I as Iterator>::Item;
fn next(&mut self) -> Option<Self::Item> {
let mut first = match self.held.take() {
Some(v) => v,
None => self.iter.next()?,
};
loop {
let second = match self.iter.next() {
Some(v) => v,
None => return Some(first),
};
match (self.func)(&first, &second) {
// If merge succeeds, attempt to merge again
Some(v) => first = v,
// If merge fails, store second value for next iteration and return result
None => {
self.held = Some(second);
return Some(first);
}
}
}
}
}
pub trait ToMergeIter: Iterator {
fn merge<F>(self, func: F) -> MergeIter<Self, F>
where
Self: Sized,
F: FnMut(&Self::Item, &Self::Item) -> Option<Self::Item>;
}
impl<I: Sized Iterator> ToMergeIter for I {
fn merge<F>(self, func: F) -> MergeIter<Self, F>
where
Self: Sized,
F: FnMut(&Self::Item, &Self::Item) -> Option<Self::Item>,
{
MergeIter {
iter: self,
func: Box::new(func),
held: None,
}
}
}
然后我們可以遞回地應用這個程序來得到我們的結果。這是一個簡短的示例，說明它的外觀。它的記憶體效率并不高，因為它Vec每次都會創建一個新指令，但它使指定要合并的指令的程序對您來說更容易，并有助于使您的作業更易于閱讀/除錯。
pub fn optimize(instructions: Vec<Instruction>) -> Vec<Instruction> {
instructions
.into_iter()
// Recursively call function on loops
.map(|instruction| match instruction {
Instruction::Loop(x) => Instruction::Loop(optimize(x)),
x => x,
})
// Merge elements using the merge iter
.merge(|a, b| {
// State if any two given elements should be merged together or not.
match (a, b) {
(Instruction::IncPtr(x), Instruction::IncPtr(y)) => {
Some(Instruction::IncPtr(x y))
}
(Instruction::DecPtr(x), Instruction::DecPtr(y)) => {
Some(Instruction::DecPtr(x y))
}
(Instruction::Increment(x), Instruction::Increment(y)) => {
Some(Instruction::Increment(x y))
}
(Instruction::Decrement(x), Instruction::Decrement(y)) => {
Some(Instruction::Decrement(x y))
}
// Etc...
_ => None,
}
})
// Collect results to return
.collect()
}
游樂場鏈接
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/452508.html